数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学二进制索引树：C++ 中的区间更新和区间查询
这里，我们得到一个大小为 n 的数组，它最初所有元素都为 0。并且需要对其执行一些查询。
update(l,r, value) − 将值添加到数组中索引 l 到 r 之间的元素。例如，update(2, 4, 5) 将更新数组，在索引 4 和 5 的元素上分别加上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] 上。sum 变量 k 将根据其相对值位于 3 个不同的区域，并且范围在更新查询的 [l,r] 内。
区域 1 − k 位于 0 和 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
更新于：2020年7月17日
326 次浏览
广告