题解 P4514 【上帝造题的七分钟】

· · 题解

二维树状数组

二维树状数组是一个十分胡扯玄妙的算法。它和一维树状数组有着相同的地方，那就是lowbit运算。在一维树状数组中，我们用tree[x]记录右端点为x，长度为lowbit(x)的区间的区间和。我们同样可以类似地定义tree[x][y]为右下端点为(x,y),高为lowbit(x),宽为lowbit(y)的区间的区间和。

那么我们如何对其进行区间修改呢？

我们回忆一下我们是如何对一维树状数组进行区间修改的。我们对其进行差分操作，是为了使得到的差分数组前缀和就等于对应位置元素的值。那么我们可以运用类比思想，设计一个二维的差分呢？

什么是差分数组呢？

对于一个数组A[ ]，其差分数组D[i]=A[i]-A[i-1] (i>0)且D[0]=A[0]

令SumD[i]=D[0]+D[1]+D[2]+…+D[i] （SumD[ ]是差分数组D[ ]的前缀和） 则SumD[i]=A[0]+A[1]-A[0]+A[2]-A[1]+A[3]-A[2]+…+A[i]-A[i-1]=A[i] 即A[i]的差分数组是D[i]， 而D[i]的前缀和是A[i]

回归正题

我们来看一下二维的前缀和。

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

查询左上角点（x1,y1），右下角点(x2,y2)的区间和则是：sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]

那么我们可以使差分数组d[i][j]等于a[i][j]和a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差。

如下矩阵:

         0 0 0 0 0
         0 0 0 0 0
         0 0 0 0 0 
         0 0 0 0 0

当我们想给中间那个2*3的矩阵加上x时，差分数组的变化应该是：

         0  0 0 0 0
         0 +x 0 0 -x
         0  0 0 0 0
         0 -x 0 0 +x

至于为什么要这样，我们要等到区间查询时就会发现。

区间查询

根据差分数组的定义，我们不难发现，对于点(x,y)，它的二维前缀和就是:

\sum_{i=1}^x\sum_{j=1}^y\sum_{h=1}^i\sum_{k=1}^j d[h][k]

但我们类比一下一维树状数组的区间求和，我们亦可以统计每个d[h][k]出现的次数，我们就可以发现d[1][1]出现了(x\times y)次，d[1][2]出现了x\times(y-1)次……d[h][k]出现了(x-h+1)\times (y-k+1)次。

则原式整理得：

\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times (x-i+1)\times (y-j+1)

分解得：

\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times [(xy-xj+x)+(-yi+ij-i)+(y-j+1)]

最后得：

\sum_{i=1}^x\sum_{j=1}^y d[i][j]\times (xy+x+y+1)-d[i][j]\times i(y+1)-d[i][j]\times j(x+1)+d[i][j]\times i\times j

根据我们最后分解出来的公式，我们需要维护四个数组d[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*j，从而实现区间查询。

例题

LuoguP4514 上帝造题的七分钟

非常适合我们的二维树状数组裸题。因为这题听说开二维线段树会爆空间，所以我们要使用二维树状数组。而且这题要开o2优化，不然过不了。惨痛的经历。原理我们已经讲得很清楚了，直接上代码。

// luogu-judger-enable-o2
#include <cstdio>

int n,m,num,x1,y1,x2,y2;
char c[3];

struct BIT
{
    int tree[2050][2050];

    int lowbit(int x) {return x&-x;}

    void add(int x,int y,int num)
    {
        for(int i=x; i<=n; i+=lowbit(i))
            for(int j=y; j<=m; j+=lowbit(j))
                tree[i][j]+=num;
    }

    int query(int x,int y)
    {
        int res=0;
        for(int i=x; i>=1; i-=lowbit(i))
            for(int j=y; j>=1; j-=lowbit(j))
                res+=tree[i][j];
        return res;
    }
}A,Ai,Aj,Aij;

int read()
{
    int sign=1,res=0;
    char c;
    while((c=getchar())<48||c>57)
        if(c=='-')
            sign=-1;
    if(sign)
        res=c-48;
    while((c=getchar())>=48&&c<=57)
        res=res*10+c-48;
    return res*sign;
}

int Ans(int x,int y)
{
    return A.query(x,y)*(x*y+x+y+1)-
           Ai.query(x,y)*(y+1)-
           Aj.query(x,y)*(x+1)+
           Aij.query(x,y);
}

void Add(int x,int y,int num)
{
    A.add(x,y,num);
    Ai.add(x,y,num*x);
    Aj.add(x,y,num*y);
    Aij.add(x,y,num*x*y);
}

int main()
{
    scanf("X %d %d",&n,&m);
    while(~scanf("%s",&c))
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(c[0]=='L')
        {
            scanf("%d",&num);
            Add(x1,y1,num);
            Add(x1,y2+1,-num);
            Add(x2+1,y1,-num);
            Add(x2+1,y2+1,num);
        }else
        {
            printf("%d\n",Ans(x2,y2)-Ans(x1-1,y2)-Ans(x2,y1-1)+Ans(x1-1,y1-1));
        }
    }
    return 0;
}

参考地址