树状数组的图是这样吗?
如果是,按照此P3368模板题AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[501000],n,m;
int lowbit(int a){
return a&-a;
}
void add(int x,int b){
while(x<=n){
t[x]+=b;
x+=lowbit(x);
}
}
int one_dfs(int x){
int sum=0;
while(x!=0){
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int l;
cin>>l;
add(i,l);
add(i+1,-l);
}
for(int i=1;i<=m;i++){
int a;
cin>>a;
if(a==1){
int x,y,k;
cin>>x>>y>>k;
add(x,k);
add(y+1,-k);
// for(int i=1;i<=5;i++) cout<<t[i]<<" ";
// cout<<endl;
}
if(a==2){
int x;
cin>>x;
cout<<one_dfs(x)<<endl;
}
}
return 0;
}
实现区间修改,在1-2间+k
按照查分,1,2,4,8会+k
2+1=3,在3,4,8会-k
t[3]是不是多-k了?