二维树状数组

裸体就意味着身体。

原本这篇博客是《P4514 上帝造题的七分钟》的题解，结果加了三道 $\text{Loj}$ 的题，标题太长，就改成二维树状数组了。

二维树状数组，简要地说，就是维护二维区间（矩阵）的运算与查询，且需要满足差分性质，如果不错的话，时间复杂度可以达到 $\mathcal O(n\log^2n)$ 。甚至可以做到二维的线段树模板一的操作，即区间修改区间查询。

我们知道：

单点修改，区间查询的树状数组：直接统计前缀和；
单点查询，区间修改的树状数组：统计差分前缀和。

那么，区间修改区间查询明明使用线段树更快捷，但事实上，这道题，线段树不可做。

网络上有两种二维线段树的写法，一种是对每一行开一棵线段树，并逐一修改，时间复杂度高达 $\mathcal O(n^2\log n)$ ，不可做；另一种写法名为四叉树，是线段树套线段树的 $\mathcal O(n\log^2n)$ 写法，但假了。

所以，这道题，只有二维树状数组可做。

那么，我们需要先统计一遍差分数组把原矩阵求出来，再统计原矩阵的和，都需要在 $\log$ 级别的时间内得到，还是有些困难。

首先考虑二维差分：

$diff[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

再考虑二维前缀和：

$sum[i][j]=-sum[i-1][j]-sum[i][j-1]+sum[i-1][j-1]+a[i][j]$

并统计原矩阵：

$a[i][j]=diff[i][j]-diff[i-1][j]-diff[i][j-1]+diff[i-1][j-1]$

得到：

$sum[i][j]=diff[i][j]-diff[i-1][j]-diff[i][j-1]+diff[i-1][j-1]-sum[i-1][j]-sum[i][j-1]+sum[i-1][j-1]$

然后得到通式，可以发现：

$\displaystyle sum[x][y]=\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{l=1}^{i}\sum_{r=1}^{j}diff[l][r]$

然后化简一下式子：

$\displaystyle sum[x][y]=\sum_{i=1}^{x}\sum_{j=1}^{y}diff[i][j]\times(x-i+1)\times(y-j+1)$

最后分解得到：

$\displaystyle sum[x][y]=\sum_{i=1}^{x}\sum_{j=1}^{y}diff[i][j]\times(xy+x+y+1)+diff[i][j]\times i(y+1)+diff[i][j]\times j(x+1)+diff[i][j]\times ij$

由于 $x,y$ 为常数，利用斜率优化的思路，我们维护四个二维树状数组，分别记录 $diff[i][j],diff[i][j]\times i,diff[i][j]\times j,diff[i][j]\times i\times j$ 的前缀值即可。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
    x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
    x=x<y?x:y;
}
const int MAXN=2e3+50;
int N,M,Q;
char opt[10];
struct Bit
{
    int Tre[MAXN][MAXN];
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    inline void add(int x,int y,int k)
    {
        for(int i=x;i<=N;i+=lowbit(i))
            for(int j=y;j<=M;j+=lowbit(j))
                Tre[i][j]+=k;
    }
    inline int query(int x,int y)
    {
        int res=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                res+=Tre[i][j];
        return res;
    }
}Dif,Difi,Difj,Difij;
inline void modify(int l,int r,int k)
{
    Dif.add(l,r,k),Difi.add(l,r,k*l),Difj.add(l,r,k*r),Difij.add(l,r,k*l*r);
}
inline int query(int l,int r)
{
    return Dif.query(l,r)*(l*r+l+r+1)-Difi.query(l,r)*(r+1)-Difj.query(l,r)*(l+1)+Difij.query(l,r);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%s",opt);read(N,M);
    while(~scanf("%s",opt+1))
    {
        if(opt[1]=='L')
        {
            int qa,qb,qc,qd;int qk;
            read(qa,qb,qc,qd,qk);
            modify(qa,qb,qk),modify(qc+1,qd+1,qk);
            modify(qc+1,qb,-qk),modify(qa,qd+1,-qk);
        }
        else
        {
            int qa,qb,qc,qd;
            read(qa,qb,qc,qd);
            write(query(qc,qd)-query(qa-1,qd)-query(qc,qb-1)+query(qa-1,qb-1),'\n');
        }
    }
    return 0;
}
/*
X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3
*/

那么，掌握了区间操作，单点操作的话，就轻轻松松了。

$\text{Loj}$ 上有三道二维树状数组的板子，分别对应洛谷一维的树状数组一，树状数组二，线段树一，可以稍微做一做。

Loj#133. AC Code

const int MAXN=4e3+100;
int N,M,Q;
char opt[10];
struct Bit
{
    ll Tre[MAXN][MAXN];
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    inline void add(int x,int y,ll k)
    {
        for(int i=x;i<=N;i+=lowbit(i))
            for(int j=y;j<=M;j+=lowbit(j))
                Tre[i][j]+=k;
    }
    inline ll query(int x,int y)
    {
        ll res=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                res+=Tre[i][j];
        return res;
    }
}Dif;
inline ll query(int l,int r)
{
    return Dif.query(l,r);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    while(~scanf("%s",opt+1))
    {
        if(opt[1]=='1')
        {
            int qa,qb;ll qk;
            read(qa,qb,qk);
            Dif.add(qa,qb,qk);
        }
        else
        {
            int qa,qb,qc,qd;
            read(qa,qb,qc,qd);
            write(query(qc,qd)-query(qa-1,qd)-query(qc,qb-1)+query(qa-1,qb-1),'\n');
        }
    }
    return 0;
}
/*
2 2
1 1 1 3
1 2 2 4
2 1 1 2 2
*/

Loj#134. AC Code

const int MAXN=4e3+100;
int N,M,Q;
char opt[10];
struct Bit
{
    ll Tre[MAXN][MAXN];
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    inline void add(int x,int y,ll k)
    {
        for(int i=x;i<=N;i+=lowbit(i))
            for(int j=y;j<=M;j+=lowbit(j))
                Tre[i][j]+=k;
    }
    inline ll query(int x,int y)
    {
        ll res=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                res+=Tre[i][j];
        return res;
    }
}Dif;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    while(~scanf("%s",opt+1))
    {
        if(opt[1]=='1')
        {
            int qa,qb,qc,qd;ll qk;
            read(qa,qb,qc,qd,qk);
            Dif.add(qa,qb,qk),Dif.add(qc+1,qd+1,qk);
            Dif.add(qa,qd+1,-qk),Dif.add(qc+1,qb,-qk);
        }
        else
        {
            int qa,qb;read(qa,qb);
            write(Dif.query(qa,qb),'\n');
        }
    }
    return 0;
}
/*
2 2
1 1 1 2 2 5
1 1 2 2 2 -3
2 1 1
2 1 2
2 2 1
2 2 2
*/

Loj#135. AC Code

const int MAXN=2e3+50;
int N,M,Q;
char opt[10];
struct Bit
{
    ll Tre[MAXN][MAXN];
    inline int lowbit(int x)
    {
        return x&(-x);
    }
    inline void add(int x,int y,ll k)
    {
        for(int i=x;i<=N;i+=lowbit(i))
            for(int j=y;j<=M;j+=lowbit(j))
                Tre[i][j]+=k;
    }
    inline ll query(int x,int y)
    {
        ll res=0;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                res+=Tre[i][j];
        return res;
    }
}Dif,Difi,Difj,Difij;
inline void modify(int l,int r,ll k)
{
    Dif.add(l,r,k),Difi.add(l,r,k*l),Difj.add(l,r,k*r),Difij.add(l,r,k*l*r);
}
inline ll query(int l,int r)
{
    return Dif.query(l,r)*(l*r+l+r+1)-Difi.query(l,r)*(r+1)-Difj.query(l,r)*(l+1)+Difij.query(l,r);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    while(~scanf("%s",opt+1))
    {
        if(opt[1]=='1')
        {
            int qa,qb,qc,qd;ll qk;
            read(qa,qb,qc,qd,qk);
            modify(qa,qb,qk),modify(qc+1,qd+1,qk);
            modify(qc+1,qb,-qk),modify(qa,qd+1,-qk);
        }
        else
        {
            int qa,qb,qc,qd;
            read(qa,qb,qc,qd);
            write(query(qc,qd)-query(qa-1,qd)-query(qc,qb-1)+query(qa-1,qb-1),'\n');
        }
    }
    return 0;
}
/*
4 4
1 1 1 3 3 2
1 2 2 4 4 1
2 2 2 3 3
*/