Binary Index Tree

二维差分:

struct matrix
{
    int c[__][__];
    int* operator[](int x){return c[x];}
    void add(int x1,int y1,int x2,int y2,int v)
    {
        c[x1][y1]+=v,c[x2+1][y2+1]+=v;
        c[x1][y2+1]-=v,c[x2+1][y1]-=v;
    }
    void cal(int n,int m)
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
    }
    void print(int n,int m)
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                printf("%d%c",c[i][j]," \n"[j==m]);
    }
}M;

单点修改/询问前缀和:

struct BinaryIndexTree
{
    int n,c[50005];
    void add(int i,int val)
    {
        for(;i<=n;i+=i&(-i))
            c[i]+=val;
    }
    int get_sum(int i)
    {
        int res=0;
        for(;i;i-=i&(-i))
            res+=c[i];
        return res;
    }
    void clear(){memset(c,0,sizeof(c));}
};

区间修改/询问区间:

struct BinaryIndexTree
{
    int n,c[100005],d[100005];
    void add(int l,int r,int val)
    {
        for(int i=l--; i<=n; i+=i&(-i))
            c[i]+=val,d[i]+=l*val;
        for(int i=r+1; i<=n; i+=i&(-i))
            c[i]-=val,d[i]-=r*val;
    }
    int get_sum(int l,int r)
    {
        int res=0;
        for(int i=r; i; i-=i&(-i))
            res+=r*c[i]-d[i];
        for(int i=--l; i; i-=i&(-i))
            res-=l*c[i]-d[i];
        return res;
    }
    void clear()
    {
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
    }
};

二维树状数组:

int n,c[1005][1005];

void update(int x,int y,int val)
{
    for(int i=x; i<=n; i+=i&(-i))
        for(int j=y; j<=n; j+=j&(-j))
            c[i][j]+=val;
}

int get_sum(int x,int y)
{
    int res=0;
    for(int i=x; i; i-=i&(-i))
        for(int j=y; j; j-=j&(-j))
            res+=c[i][j];
    return res;
}