二维树状数组基础

NBest · 2023-08-10 11:04:41 · 个人记录

二维树状数组

二维树状数组与一维树状数组其实原来差不多，相当于对整个列开一个树状数组，然后对其中每一行开一个树状数组。所以其基本形式与一维树状数组差不多，非常好理解（可以看做是行列相互独立，只是处理行的时候处理的是其对应的列的树状数组，学了二维线段树应该可以更好地理解）。

基本代码:

ll a[N][M];
void add(int x,int w,int v){
    for(;x<=n;x+=lb(x))
        for(int y=w;y<=m;y+=lb(y))
            a[x][y]+=v;
}
ll query(int x,int w){
    ll res=0;
    for(;x;x-=lb(x))
        for(int y=w;y;y-=lb(y))
            res+=a[x][y];
    return res;
}

对于一维树状数组，我们用 query(x) 函数查找的是 [1,x] 的前缀和，那么同理类比二维树状数组，我们使用 query(x,y) 查找的是 (x,y) 的二维前缀和，也就是左上角为 (1,1)，右下角为 (x,y) 的矩阵内所有内容的和。

单点修改，区间查询

例题：LOJ#133 二维树状数组 1：单点修改，区间查询

就用之前写没有修改的矩阵前缀和公式即可：（(x1,y1) 右下角,(x2,y2) 左下角）

//单点修改
add(x,y,v);
//区间查询
ans=query(x1,y1)-query(x2-1,y1)-query(x1,y2-1)+query(x2-1,y2-1);

区间修改，单点查询

例题：LOJ#134 二维树状数组 2：区间修改，单点查询

其实就是一个二维差分的转换，其他的基本与上面一致。

//区间修改，不理解可以自己画个图(a,b左上,c,d右下)
add(a,b,k);
add(a,d+1,-k);
add (c+1,b,-k);
add(c+1,d+1,k);
//单点查询
ans=query(a,b);

区间修改，区间查询

其实个人认为如果对空间要求不大的话，可以直接用二维线段树写，比较直观，而且更好理解，但是如果空间被卡了 (正睿打模拟赛： n,m\le8000，内存开 400MB，模数很小,\le 256，可以用 char 或者 short)，那只能用空间少了最少 16 倍的树状数组了。（线段树每维都得开四倍以上）

勘误：

short 是 2 个字节的带符号短整型数，能表示 [-32768,+32767]，对于这道题，我们要开 4\times 8000\times 8000 大小的数组，如果用 short 存，内存约为 500 MB，显然爆空间。
而 char 取值范围为 [-128,+127],这意味着如果你用 char 做这道题直接会爆 0。
正确做法是用 unsigned char，取值范围 [0,255]，刚好满足模数要求，而内存基本上为 250 MB 左右，可以通过此题，但是要及其小心赋值过程中可能出现的爆精度问题，具体代码详见模拟赛C题题解。

在写二维树状数组的区间修改，区间查询时，我们先看看一维的怎么做。

一维树状数组的区间修改，区间查询

首先我们得先用差分的方法维护出一个差分序列 d[]，然后我们不难发现，想求 [1,n] 的值，我们只需要求差分数组的前缀和的前缀和，即 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}d[j]。

接下来我们不难推得：

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}d[j]\\\sum\limits_{i=1}^{n}(n-i+1)d[i]\\\sum\limits_{i=1}^{n}(n+1)d[i]-i\times d[i]\\(n+1)\sum\limits_{i=1}^{n}d[i]-\sum\limits_{i=1}^{n}i\times d[i]

所以我们只需要分别处理 d[i] 和 i\times d[i] 即可。

例题：LOJ #132. 树状数组 3 ：区间修改，区间查询

Code

#define lb(x) (x&-x)
int n,q;
ll a[1000006],ia[1000006];//a[]维护 d[]，ia[] 维护 i*d[]。
void add(int x,int v){
    for(int i=x;x<=n;x+=lb(x))
        a[x]+=v,ia[x]+=1ll*i*v;
}
ll query(int x){
    ll res=0;
    for(int i=x+1;x;x-=lb(x))
        res+=a[x]*i-ia[x];
    return res;
}
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        int v=read();
        add(i,v),add(i+1,-v);//加入初点
    }
    while(q--){
        int opt=read(),l=read(),r=read();
        if(opt&1){
            int v=read();
            add(l,v),add(r+1,-v);//区间修改差分
        }else{
            printf("%lld\n",query(r)-query(l-1));//区间查询
        }
    }
}

二维树状数组的区间修改，区间查询

与一维类似，我们仍然维护二维差分数组 d[][]，那么点 (x,y) 的前缀和为：

\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}\sum\limits_{u=1}^{i}\sum\limits_{v=1}^{j}d[u][v]\\\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}(x+1-i)(y+1-j)d[i][j]\\\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}((x+1)(y+1)-j(x+1)-i(y+1)+ij)d[i][j]\\(x+1)(y+1)\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}d[i][j]-(x+1)\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}j\times d[i][j]-(y+1)\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}i\times d[i][j]+\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}ij\times d[i][j]

所以我们只需要分别处理 d[i][j],j\times d[i][j],i\times d[i][j],ij\times d[i][j] 即可。

例题LOJ #135. 二维树状数组 3：区间修改，区间查询

Code

#define lb(x) (x&-x)
ll d[N][N],id[N][N],jd[N][N],ijd[N][N];//四个部分分开处理
void add(int x,int y,ll v){//修改 (x,y) 的差分
    for(int i=x;i<=n;i+=lb(i))
        for(int j=y;j<=m;j+=lb(j)){
            d[i][j]+=v;
            id[i][j]+=v*x;
            jd[i][j]+=v*y;
            ijd[i][j]+=v*x*y;
        }
}
ll query(int x,int y){//查询 (x,y) 的前缀
    ll res=0;
    for(int i=x;i;i-=lb(i))
        for(int j=y;j;j-=lb(j)){
            res+=(x+1)*(y+1)*d[i][j]-(x+1)*jd[i][j]-(y+1)*id[i][j]+ijd[i][j];
        }
    return res;
}
//区间修改
void update(int x1,int y1,int x2,int y2,ll v){
    add(x1,y1,v);
    add(x1,y2+1,-v);
    add(x2+1,y1,-v);
    add(x2+1,y2+1,v);
    return;
}
//区间查询
ll Query(int x1,int y1,int x2,int y2){
    return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1);
}

后话

打完模拟赛被薄纱了来学的，因为只想到二维线段树可做，没想到树状数组还可以做到区间查询，区间修改的吗，以前真不知道唉。