题解 P3368 【【模板】树状数组 2】

Drug__Lover

2017-10-23 20:24:44

Solution

**楼下众神犇好像都用了一个这个东西** ```cpp change(i,a1[i]-a1[i-1]); ``` **对于蒟蒻的我当时并不理解** **只好半懵逼半清醒的抄上AC了** **很久之后的现在又来做了一下这道题** **发现了一个好理解的?(题解并没有看到底,不知道有没有重复的)** **对于修改我们可以用树状数组维护差分数组** **但是用树状数组我们仅维护修改的值(也就是改变的值)** **最后查询的时候加上初始值就好了** ```cpp #include<iostream> #include<cstdio> #define maxn 500100 using namespace std; int n,m; int c[maxn]; int a[maxn]; int add(int x,int k) { for(int i=x;i<=n;i+=i&(-i)) c[i]+=k; } int query(int x) { int sum=0; for(int i=x;i>0;i-=i&(-i)) sum+=c[i]; return sum; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(m--) { int k; scanf("%d",&k); if(k==1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,z); //维护查分数组 add(y+1,-z); } else { int x; scanf("%d",&x); printf("%d\n",a[x]+query(x)); //query()求的是改变的值,再加上原来的值就可以了 } } return 0; } ```