バイナリインデックスツリー：C++での範囲の更新と範囲のクエリ

ここでは、最初はすべての要素が0であるサイズnの配列が与えられています。また、その配列に対して実行されるクエリがいくつかあります。クエリには2つのタイプがあります-

• update（l、r、value） −インデックスlからrの間にある配列の要素に値を追加します。たとえば、update（2、4、5）は、要素2をインデックス4と5の要素に配置することで配列を更新します。

• getRangeSum（l、r） −lからrまでの要素の範囲内の要素の合計を求めます。たとえば、getRangeSum（4、7）は、インデックス4、5、6、7のすべての要素の合計を検索します。

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

入力

n = 7 , arr[7] = {0,0,0,0,0,0,0}
Q1 = update(3, 6, 4)
Q2 = update(0, 4, 2)
Q3 = Sum(2, 5)

出力

10

説明

Solving queries: Q1 - update(3, 6, 4) = {0, 0, 0, 4, 4, 4, 4}
Q2 - update(0, 4, 2) = {2, 2, 2, 2, 2, 4, 4}
Q3 - sum(2, 5) = 2+2+2+4 = 10

この問題を解決するための単純なアプローチは、更新クエリごとに配列を更新してから合計を見つけることですが、これはそれほど効果的ではないため、問題を解決するためのより効果的なアプローチを学びましょう。

合計クエリに対する更新クエリの影響を見てみましょう。合計クエリはsum[l、r]の形式です。これを、sum [0、k]の形式の合計クエリに分割し、合計から下限までの合計を減算します。

sum[l,r] = sum[0,r] - sum[0,l]

したがって、sum [0、k]の効果はsum [l、r]に反映されます。合計変数kは、その相対値に基づいて3つの異なる領域に存在し、更新クエリの範囲[l、r]になります。

リージョン1 − kはoとlの間にあります。つまり、0

この場合、更新クエリは合計クエリに影響しません。

リージョン2 − kはlとrの間にあります。つまり、l≤k≤r

この場合、合計クエリはlからkまでの値を楽しませます。

リージョン3 − kはrより大きい、つまりk> r

この場合、合計クエリはlからrまでのすべての値を楽しませます。

それでは、範囲の更新と範囲のクエリを解決するプログラムを見てみましょう

//範囲の更新と範囲のクエリを解決するプログラム

例

#include <bits/stdc++.h>
using namespace std;
int getSum(int BITree[], int i){
   int sum = 0;
   i++;
   while (i>0) {
      sum += BITree[i];
      i -= i & (-i);
   }
   return sum;
}
void updateBITree(int BITree[], int n, int i, int val) {
   i = i + 1;
   while (i <= n) {
      BITree[i] += val;
      i += i & (-i);
   }
}
void update(int BITTree1[], int BITTree2[], int n, int l, int r, int value) {
   updateBITree(BITTree1,n,l,value);
   updateBITree(BITTree1,n,r+1,-value);
   updateBITree(BITTree2,n,l,value*(l-1));
   updateBITree(BITTree2,n,r+1,-value*r);
}
int sum(int x, int BITTree1[], int BITTree2[]) {
   return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);
}
int getRangeSum(int l, int r, int BITTree1[], int BITTree2[]) {
   return sum(r, BITTree1, BITTree2) - sum(l-1, BITTree1, BITTree2);
}
int *createBITree(int n) {
   int *BITree = new int[n+1];
   for (int i=1; i<=n; i++)
   BITree[i] = 0;
   return BITree;
}
int main(){
   int n = 7;
   int *BITTree1, *BITTree2;
   BITTree1 = createBITree(n);
   BITTree2 = createBITree(n);
   update(BITTree1,BITTree2,n,3,6,9);
   update(BITTree1,BITTree2,n, 0, 4, 5);
   cout<<"The output of sum query after applying all update queries is \t"      <<getRangeSum(1,5,BITTree1,BITTree2);
   return 0;
}

出力

The output of sum query after applying all update queries is