数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用树状数组（离线查询）查找区间 L 到 R 中大于 K 的元素个数
在计算机科学领域，我们必须处理大型数据集，这包括查询选择和更新操作。对于开发人员来说，以较低的时空复杂度实时执行这些操作是一项具有挑战性的任务。
使用树状数组是解决这些基于范围的查询问题的有效方法。
树状数组是一种数据结构，它可以高效地更新元素并计算表中数字的前缀和。它也称为二进制索引树。
在本文中，我们将讨论如何使用树状数组查找区间 L 到 R 中大于 K 的元素个数。
输入输出场景
假设你有一个包含 N 个元素的数组，你想找到数组中区间 L 到 R 内大于 K 的元素个数。
Input:
arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}
N = 11, K = 17, L = 1, R = 8
Output:
2
什么是离线查询？
离线查询是在预定数据集上执行的查询操作。换句话说，这些操作仅在对数据集没有进一步修改的情况下进行。
使用树状数组
在这里，我们将使用一个树状数组，其每个节点都包含数组中所有元素的有序向量。然后，我们使用二分查找来回答每个查询并计数元素。
创建两个函数 `updateTree()` 和 `total()`，分别用于更新和检索**BIT**中的前缀和。
接下来，创建另一个函数来计算区间 L 到 R 中大于 'K' 的元素个数。此函数接收 'arr'、'N'、'L'、'R' 和 'K' 的输入值。
计数通过从最大范围 N 的累积和中减去 K 的累积和来计算。
为了排除范围外的元素，它会减去 L-1 的累积和（如果 L 大于 1）。
示例
#include <iostream>
#include <vector>
using namespace std;
// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
while (index < BIT.size()) {
BIT[index] += value;
index += index & -index;
}
}
int total(vector<int>& BIT, int index) {
int result = 0;
while (index > 0) {
result += BIT[index];
index -= index & -index;
}
return result;
}
// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
vector<int> BIT(N+1, 0);
for (int i = L; i <= R; i++) {
updateTree(BIT, arr[i], 1);
}
int count = total(BIT, N) - total(BIT, K);
if (L > 1) {
count -= total(BIT, L-1);
}
return count;
}
int main() {
vector<int> arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9};
int N = 11; // Total range of values
int K = 4; // Highest value
int L = 1; // Start index of the range
int R = 8; // End index of the range
int count = elementsGreaterThanK(arr, N, K, L, R);
cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl;
return 0;
}
输出
Number of elements greater than 4 in the range [1, 8]: 5
替代方法
在这里，我们将创建一个单独的向量来存储查询。每个查询包含两个变量，`index` 和 `val`。`index` 用于存储数组中的位置，而 `val` 用于存储该索引处元素的值。这种方法使开发人员能够执行各种查询操作。此外，我们使用 BIT 计算每个查询中大于 `K` 的元素个数。
示例
#include <iostream>
#include <vector>
using namespace std;
struct Query {
int index;
int val;
};
void updateTree(vector<int>& BIT, int index, int value) {
while (index < BIT.size()) {
BIT[index] += value;
index += index & -index;
}
}
int total(vector<int>& BIT, int index) {
int result = 0;
while (index > 0) {
result += BIT[index];
index -= index & -index;
}
return result;
}
vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
int N = arr.size();
vector<int> BIT(N+1, 0);
vector<int> result;
for (int i = 0; i < N; i++) {
updateTree(BIT, i+1, (arr[i] > K) ? 1 : 0);
}
for (auto query : queries) {
if (query.val > K) {
result.push_back(total(BIT, query.index));
}
else {
result.push_back(0);
}
}
return result;
}
int main() {
vector<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
int K = 2;
vector<int> counts = elementsGreaterThanK(arr, queries, K);
for (int count : counts) {
cout << "Number of elements greater than " << K << ": " << count << endl;
}
return 0;
}
输出
Number of elements greater than 2: 2 Number of elements greater than 2: 5 Number of elements greater than 2: 3 Number of elements greater than 2: 0
结论
我们可以简单地迭代数组从索引 L 到 R，并在数组元素大于 K 时递增 1，以找到每个查询的答案。但是，为了降低时间复杂度，我们对这种类型的查询操作使用**树状数组**。除了树状数组之外，我们还可以使用**线段树**和**稀疏表**来进行此类查询操作。
浏览量：275
