BZOJ1452: [JSOI2009]Count 二维树状数组

本文转载自 oakley_ 查看原文 2016/10/13 256 二维树状数组/ BZOJ

BZOJ 1452: [JSOI2009]Count

Time Limit: 10 Sec Memory Limit: 64 MB

Submit: 2095 Solved: 1233

题解： 二维树状数组裸题二维树状数组：先回想一下一维树状数组，c[i]表示一维平面上a[i-lowb(i)+1]~a[i]的值再来看二维树状数组，c[i][j]表示在二维平面上:左上角坐标为(i-lowbit(i)+1，j-lowbit(j)+1),右下角坐标为(i，j)的矩阵内的元素和，二维树状数组与一维树状数组具有同样的性质（具体想想明白只需要自己话一个矩形就好啦，很有助于理解）本题：因为颜色数小于100，可以对每一种颜色维护一个二维树状数组，空间上也可以接受。其它就和一维树状数组一样，只不过多了一层循环，单次查询或者修改的复杂度变成了（logn*logn）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
int n,m,q,mp[N][N],c[105][N][N];
void Modify(int x,int y,int col,int val)
{
     for(int i=x;i<=n;i+=(i&-i))
     for(int j=y;j<=m;j+=(j&-j))
     c[col][i][j]+=val;
}
int Query(int x,int y,int col)
{
    int tmp=0;
    for(int i=x;i;i-=(i&-i))
    for(int j=y;j;j-=(j&-j))
    tmp+=c[col][i][j];
    return tmp;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&mp[i][j]);
        Modify(i,j,mp[i][j],1);
    }
   	scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int o,x1,y1,x2,y2,c;
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d%d",&x1,&y1,&c);
            Modify(x1,y1,mp[x1][y1],-1);
            Modify(x1,y1,c,1);
            mp[x1][y1]=c;
        }
        else 
        {
        	scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
            printf("%d\n",Query(x2,y2,c)-Query(x1-1,y2,c)-Query(x2,y1-1,c)+Query(x1-1,y1-1,c));
        }
    }
}