树状数组

单点添加，区间查询

#include<cstdio> #include<iostream> #define M 500010 using namespace std; int a[M],tarr[M],n,m; int Qry_tarr(int pos) { int sum=0; while(pos) { sum+=tarr[pos]; pos-=(pos^(pos-1))&pos; } return sum; } void Add_tarr(int pos,int delta) { while(pos<=n) { tarr[pos]+=delta; pos+=(pos^(pos-1))&pos; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) Add_tarr(i,a[i]); int flag,x,y; for(int i=1;i<=m;i++) { scanf("%d%d%d",&flag,&x,&y); if(flag==1)Add_tarr(x,y); else printf("%d\n",Qry_tarr(y)-Qry_tarr(x-1)); } return 0; }

区间修改，单点查询（差分）

#include<iostream>//区间修改，单点查询 using namespace std; #define M 500010 int tr[M],b[M],n; int search(int pos) { int sum=0; while(pos) { sum+=tr[pos]; pos-=(pos^(pos-1))&pos; } return sum; } void add(int pos,int v) { while(pos<=n) { tr[pos]+=v; pos+=(pos^(pos-1))&pos; } } int main() { cin>>n; int a=0,c=0; for(int i=1;i<=n;i++) { cin>>a; b[i]=a-c; c=a; } for(int i=1;i<=n;i++) add(i,b[i]); cin>>a; cout<<search(a); }