树状数组差分
2025-07-16 21:10:40
发布于：浙江
25阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],f[500005];
int lowbit(int x){
return x&-x;
}
void add(int x,int p){
while(x<=n)f[x]+=p,x+=lowbit(x);
}
int ask(int x){
int ans=0;
while(x>0)ans+=f[x],x-=lowbit(x);
return ans;
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> a[i];
while(m--){
int q,x,y,z;
cin >> q;
if(q==1){
cin >> x >> y >> z;
add(x,z),add(y+1,-z);
}else{
cin >> x;
cout << ask(x)+a[x] << endl;
}
}
}
有帮助，赞一个