二维树状数组

TH讠NK · 2019-08-04 18:24:34 · 个人记录

二维树状数组维护二维前缀和

inline void add(int x,int y,int w){
    for(int i=x;i<=n;i+=(i&-i))
        for(int j=y;j<=m;j+=(j&-j)){
            c[0][i][j]+=w;
            c[1][i][j]+=w*y;
            c[2][i][j]+=w*x;
            c[3][i][j]+=w*x*y;
    }
}

inline int ask(int x,int y){
    int ans=0;
    for(int i=x;i;i-=(i&-i))
        for(int j=y;j;j-=(j&-j))
            ans+=x*y*c[0][i][j]-x*c[1][i][j]-y*c[2][i][j]+c[3][i][j];
    return ans;
}

设矩阵左下角为 (a,b) ,右上角为 (c,d)

add(a-1,b-1,w);
add(c,b-1,-w);
add(a-1,d,-w);
add(c,d,w);

ask(c,d)-ask(a-1,d)-ask(c,b-1)+ask(a-1,b-1)