二维树状数组总结&&【洛谷P4514】上帝造题的七分钟

P4514 上帝造题的七分钟

题目描述

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了00的n×mn×m矩阵。

第二分钟，L说，要能修改，于是便有了将左上角为(a,b)(a,b)，右下角为(c,d)(c,d)的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造裸题的七分钟》

所以这个神圣的任务就交给你了。

二维树状数组裸题。

定义二维差分数组：

\[d(i)(j)=a(i)(j)-a(i-1)(j)-a(i)(j-1)+a(i-1)(j-1)
\]

如何维护\(1,1\)到\(i,j\)的二维前缀和？

\[sum(x)(y)=\sum_{i=1}^x\sum_{j=1}^y\sum_{k=1}^i\sum_{l=1}^jd(i)(j)\\
=\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*(x+1-i)*(y+1-i)\\
=(x+1)*(y+1)*\sum_{i=1}^x\sum_{j=1}^yd(i)(j)-(y+1)\sum_{i=1}^x\sum_{j=1}^yd(i)(j)*i\\-(x+1)*\sum_{i=1}^x\sum_{j=1}^y*j+\sum_{i=1}^x\sum_{j=1}^y*d(i)(j)*i*j
\]

按照上述式子维护四个前缀和数组即可。

具体操作：

code:

void add(int posx,int posy,int k){

    for(int i=posx;i<=n;i+=(i&-i)){

        for(int j=posy;j<=m;j+=(j&-j)){

            sum1[i][j]+=k;

            sum2[i][j]+=k*posx;

            sum3[i][j]+=k*posy;

            sum4[i][j]+=k*posx*posy;

        }

    }

}

int query(int posx,int posy){

    int re=0;

    for(int i=posx;i>=1;i-=(i&-i)){

        for(int j=posy;j>=1;j-=(j&-j)){

            re+=((posx+1)*(posy+1))*sum1[i][j]-(posy+1)*sum2[i][j]-(posx+1)*sum3[i][j]+sum4[i][j];

        }

    }

    return re;

}

void add_wx(int x1,int x2,int y1,int y2,int k){

    add(x1,y1,k);

    add(x1,y2+1,-k);

    add(x2+1,y1,-k);

    add(x2+1,y2+1,k);

}

int query_wx(int x1,int x2,int y1,int y2){

    return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);

}

针对本题：

code：

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

using namespace std;

const int wx=3017;

inline int read(){

    int sum=0,f=1; char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

    return sum*f;

}

int sum1[wx][wx];

int sum2[wx][wx];

int sum3[wx][wx];

int sum4[wx][wx];

int n,m;

char opt[4];

/*

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

sum1[i][j]-->d[i][j]

sum2[i][j]-->d[i][j]*i

sum3[i][j]-->d[i][j]*j

sum4[i][j]-->d[i][j]*i*j

sum[x1][y1][x2][y2]=(x+1)*(y+1)*sum1[i][j]-(y+1)*sum2[i][j]-(x+1)*sum3[i][j]+sum4[i][j]。 

*/

void add(int posx,int posy,int k){

    for(int i=posx;i<=n;i+=(i&-i)){

        for(int j=posy;j<=m;j+=(j&-j)){

            sum1[i][j]+=k;

            sum2[i][j]+=k*posx;

            sum3[i][j]+=k*posy;

            sum4[i][j]+=k*posx*posy;

        }

    }

}

int query(int posx,int posy){

    int re=0;

    for(int i=posx;i>=1;i-=(i&-i)){

        for(int j=posy;j>=1;j-=(j&-j)){

            re+=((posx+1)*(posy+1))*sum1[i][j]-(posy+1)*sum2[i][j]-(posx+1)*sum3[i][j]+sum4[i][j];

        }

    }

    return re;

}

void add_wx(int x1,int x2,int y1,int y2,int k){

    add(x1,y1,k);

    add(x1,y2+1,-k);

    add(x2+1,y1,-k);

    add(x2+1,y2+1,k);

}

int query_wx(int x1,int x2,int y1,int y2){

    return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);

}

int main(){

    scanf("%s");

    n=read(); m=read();

    while(scanf("%s",opt+1)!=EOF){

        if(opt[1]=='L'){

            int x,y,z,c,k;

            x=read(); y=read(); z=read(); c=read(); k=read();

            add_wx(x,z,y,c,k);

        }

        else{

            int x,y,z,c;

            x=read(); y=read(); z=read(); c=read();

            printf("%d\n",query_wx(x,z,y,c));

        }

    }

    return 0;

}

巴特西

二维树状数组总结&&【洛谷P4514】上帝造题的七分钟

P4514 上帝造题的七分钟

题目描述

最新文章

热门文章

巴特西

二维树状数组总结&&【洛谷P4514】 上帝造题的七分钟

P4514 上帝造题的七分钟

题目描述

最新文章

热门文章

二维树状数组总结&&【洛谷P4514】上帝造题的七分钟