树状数组（二）【区间修改，单点查询】

【区间修改，单点查询】

区间修改
考虑一个数组，频繁的进行区间（l~r）修改，这时候我们会利用差分数组，(关于差分数组 ) 因为只需要修改 l 和r+1就可以，复杂度O(1)，最后求个前缀和即可。树状数组进行区间修改也一样可以用差分数组来实现。
我们维护一个差分数组，这个差分数组不需要是原数组的差分数组，可以当做是当前变化量的差分数组。显然在初始阶段，没有对任何区间做任何操作，所以这个差分数组全部是0。这样也是方便单点查询，因为这个差分数组的前缀和就是当前值的变化量。
举个例子：

   原数组a：      4  1  2  5  6
变化量的差分数组t：0  0  0  0  0  （刚开始都是0）
下面对原数组第2~4个元素+2
变化量的差分数组t：0  2  0  0  -2 
差分数组前缀和t：  0  2  2  2  0
可以发现求完前缀和正好是进行的修改操作。
如果要求某一个位置现在的值，只需要a[i]+t[i]

所以我们维护这个差分数组就好，区间修改其实也就修改两个点，所以操作就是单点修改的操作。
因为初始的差分数组全是0，所以还不用建树了。

单点查询
根据上面的例子，首先求前缀和，这也是个基本操作，区间查询里也用到过，之后与原数组的那个点相加就是最后结果。

实现也比较简单。
洛谷模板题：树状数组2
代码：

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define lowbit(x) ((x)&(-x))
typedef long long ll;

const int MXN = 5e5+5;
int a[MXN],t[MXN];  //a是原数组。t是差分数组，用树状数组维护。
int n,m;
void update(int l,int r,int x)  //区间修改，l~r变化了x
{
    while(l<=n){        //t[l]+x
        t[l]+=x;
        l+=lowbit(l);
    }
    r++;                //t[r+1]-x
    while(r<=n){
        t[r]-=x;
        r+=lowbit(r);
    }
}
int getsum(int k)       //求差分数组前缀和
{
    int sum=0;
    while(k>0){
        sum+=t[k];
        k-=lowbit(k);
    }
    return sum;
}
int main()
{
    scanf("%d %d",&n,&m);
    rep(i,1,n+1) scanf("%d",&a[i]);
    int p,l,r,x,k;
    rep(i,0,m){
        scanf("%d",&p);
        if(p==1){
            scanf("%d %d %d",&l,&r,&x);
            update(l,r,x);
        }
        else{
            scanf("%d",&k);
            printf("%d\n",a[k]+getsum(k));  //求某点的值
        }
    }
    return 0;
}