在C ++中查询值在给定范围内的数组元素的计数
在这个问题中，我们给了数组arr[]和Q查询，每个查询可以是两种类型之一，
{1，L，R}－用于[L，R]范围内的数组元素计数。
{2，index，val}-用val更新index处的元素。
我们的任务是创建一个程序来解决C++中具有给定范围值的数组元素计数的查询。
让我们举个例子来了解这个问题，
输入：arr[]={1，5，2，4，2，2，3，1，3}
Q=3
查询={{1，4，8}，
{2，6，5}，
{1，1，4}}
份数：37
说明
查询1：对范围为[4，8]的数组元素进行计数。计数=1
查询2：更新元素arr[6]=5。新数组arr[]={1、5、2、4、2、2、5、1、3}
查询1：对范围为[4，8]的数组元素进行计数。计数=7
解决方法
解决该问题的一种简单方法是直接遍历数组并查找在范围内的所有元素，即L=<element=<R。
示例
#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
int ValueCount = 0;
for (int i = 0; i < N; i++) {
if (arr[i] >= L && arr[i] <= R) {
ValueCount++;
}
}
return ValueCount;
}
int main() {
int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
}输出结果
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7
该解决方案的每个循环迭代一次。因此，其时间复杂度约为O（Q*N）。
解决此问题的更好方法是使用二进制索引树或Fenwick树数据结构。在这里，我们将数组的元素存储在树中，这将使我们能够将数组元素用作索引。而且，我们可以使用针对数据结构内置的getSum函数轻松找到范围元素的数量。
ElementCount[L，R]=getSum(R)-getSum(L-1)
示例
#include <iostream>
using namespace std;
class BinaryIndTree {
public:
int* BIT;
int N;
BinaryIndTree(int N) {
this->N = N;
BIT = new int[N];
for (int i = 0; i < N; i++) {
BIT[i] = 0;
}
}
void update(int index, int increment) {
while (index < N) {
BIT[index] += increment;
index += (index & -index);
}
}
int calcSum(int index) {
int sum = 0;
while (index > 0) {
sum += BIT[index];
index -= (index & -index);
}
return sum;
}
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree*fenwickTree){
int removedElement = arr[index];
fenwickTree->update(removedElement, -1);
arr[index] = val;
fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree*
fenwickTree) {
return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
int N = 100001;
BinaryIndTree* fenwickTree = new BinaryIndTree(N);
for (int i = 0; i < n; i++)
fenwickTree->update(arr[i], 1);
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2],fenwickTree)<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
}
}
return 0;
}输出结果
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7