C++で指定された範囲の値を持つ配列要素のカウントのクエリ

この問題では、配列arr []とQクエリが与えられ、それぞれが2つのタイプのいずれかになります。

• {1、L、R}-範囲[L、R]の配列要素の数。

• {2、index、val}-インデックスの要素をvalで更新します。

私たちのタスクは、C++で指定された範囲の値を持つ配列要素のカウントのクエリを解決するプログラムを作成することです。

問題を理解するために例を見てみましょう

入力 ：arr [] ={1、5、2、4、2、2、3、1、3}

Q =3

クエリ={{1、4、8}、

{2、6、5}、

{1、1、4}}

出力 ：3 7

説明

クエリ1：範囲[4、8]の配列要素をカウントします。カウント=1

クエリ2：要素arr [6]=5を更新します。新しい配列arr[]={1、5、2、4、2、2、5、1,3}

クエリ1：範囲[4、8]の配列要素をカウントします。カウント=7

ソリューションアプローチ

この問題の簡単な解決策は、配列を直接トラバースして、範囲内にあるすべての要素を見つけることです。つまり、L =

例

#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

アプローチするソリューションは、ループごとに1回繰り返されます。したがって、その時間計算量はO（Q * N）のオーダーです。

問題を解決するためのより良いアプローチは、BinaryIndexedTreeまたはFenwickTreeデータ構造を使用することです。ここでは、配列の要素をツリーに格納します。これにより、配列の要素をインデックスとして使用できるようになります。また、データ構造に組み込まれているgetSumfunctionを使用して、範囲の要素の数を簡単に見つけることができます。

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