二叉索引树：C++ 中的范围更新和范围查询

在这里，我们得到一个大小为 n 的数组，它最初的所有元素都是 0。并且要对其执行一些查询。有两种类型的查询 -

• 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 查询的影响。Sum 查询的形式为 sum[l,r]，我们将其拆分为 sum[0,k] 形式的 sum 查询，然后从 sum to lower limit 中减去 sum to the lower limit。

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

因此， sum[0,k] 的影响将反映在 sum[l,r] 上。总和变量 k 将基于其相对值位于 3 个不同的区域，并将在更新查询的 [l,r] 范围内。

区域 1 − k 位于 o 和 l 之间，即 0 < k < l

在这种情况下，更新查询不会影响总和查询。

区域 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