【模板】树状数组（区间修改+单点查询）

用到了差分。

对于原序列(a[])，我们的差分数组(c[])，有(c[i]=a[i]-a[i-1])

在差分玄学中，我们有(a[j]=sum_{i=1}^j c[i])

修改区间时，例如将区间(x...y)加上一个值(delta)，就直接 (c[x]+=delta; c[y+1]-=delta) 实现。

于是我们的

单点查询(----->)求查分数组前缀和

区间修改(----->)修改两点

是不是就可以套树状数组区间求和单点修改的模板了qwq！！！

#include <iostream>
using namespace std;
int n,m;
int c[500001]={};
int lowbit(int a){return a&-a;}
void add(int k,int x)
{
    while (k<=n)
    {
        c[k]+=x;
        k+=lowbit(k);
    }
    return;
}
int num(int xd)
{
    int sum=0;
    while (0<xd)
    {
        sum+=c[xd];
        xd-=lowbit(xd);
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    int first,next;
    cin>>first;
    add(1,first);
    for (int i=2;i<=n;i++)
    {
        cin>>next;
        add(i,next-first);
        first=next;
    }
    for (int i=1;i<=m;i++)
    {
        int s;
        cin>>s;
        if (s==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            add(x,k);
            add(y+1,-k);
            continue;
        }
        int x;
        cin>>x;
        cout<<num(x)<<endl;
    }
    return 0;
}