我们创建如下的树状数组来辅助操作
该数组每个s[i]处于第几层取决于其二进制 最后低位 的1处于从右往左数第几列
显然所有奇数的最右边一位都是1 即其最低位的1 处于右边第一列
所以所有的奇数处于第一层
而2，6，10，14的最低位1处于右边第二列 所以这些数处于第二层
8 的最低位1处于右数第三列 所以8处于第三列
以此类推
该结构的好处在于 如果我们只修改单个元素 的值
只需要 logn 的次数就可以完成对单元素及其区间和的修改
例如 对3进行修改
只需要三次操作 即可修改该元素 并且完成s[4] ,s[8],s[16]的前缀和的修改
而一般前缀和则需要修改 16次
至于想查看a[1-7]的和怎么办 此时只修改了s[4]并没有修改s[7]
这个疑问等会看我们的查询函数即可
先看修改的实现
我们在修改的时候往上一层 层层修改即可
使用 lowbit 函数返回查询数的最后一位1的大小
int lowbit(int x){
return x&-x;
}
修改函数
void change (int x,int k){
while(x<=n){
s[x]+=k;//上述例子的s[4],s[8],s[16]
x+=lowbit(x);//依据层次不同 1 的最低位不同更换x的位置
}
}
查询函数
我们想查询a[1]+a[2]+...+a[7]
如图只需s[7]+s[6]+s[4]即可
并且我们上面提到 虽然我们只修改了s[3],s[4]
但是我们此时算区间和的时候 加上了s[4]
所以仍然完成了对a[1]+a[2]+...+a[7]的区间和的修改
int query(int x){
int res=0;
while(x){
res+=s[x];
x-=lowbit(x);//根据我们建立层数的特性改变X
}
return res;
}
完整代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<sstream>
using namespace std;
const int N=1e8+10;
int n,m;
int a[N],s[N];
int lowbit(int x){
return x&-x;
}
void change (int x,int k){
while(x<=n){
s[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x){
res+=s[x];
x-=lowbit(x);
}
return res;
}
int main(){
/*for(int i=2;i<=16;i+=2){
cout<<i<<"的二进制最后一位为"<<lowbit(i)<<endl;
}*/
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
change(i,a[i]);
}
while(m--){
int x,y,z;
cin>>x>>y>>z;
if(x==1){
change(y,z);
}else{
cout<<query(z)-query(y-1)<<endl;
}
}
return 0;
}