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

楼下众神犇好像都用了一个这个东西

change(i,a1[i]-a1[i-1]); 

对于蒟蒻的我当时并不理解

只好半懵逼半清醒的抄上AC了

很久之后的现在又来做了一下这道题

发现了一个好理解的？（题解并没有看到底，不知道有没有重复的）

对于修改我们可以用树状数组维护差分数组

但是用树状数组我们仅维护修改的值（也就是改变的值）

最后查询的时候加上初始值就好了

#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;
}