首页 > 代码库 > TreeArray2155

TreeArray2155

 

 

 

一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为: 

 

  C[x][y] = ∑ a[i][j], 其中, 

    x-lowbit(x) + 1 <= i <= x, 

y-lowbit(y) + 1 <= j <= y.

 

在二维情况下,如果修改了A[i][j]=delta,则对应的二维树状数组更新函数为:

因为c[x][y]是以下节点的子节点:

c[x][y+lowbit(y)],c[x][y+2*lowbit(y)],c[x][y+3*lowbit(y)].... c[x][y+lengthy]

c[2*x][y+lowbit(y)],c[2*x][y+2*lowbit(y)].....

 private void Modify(int i, int j, int delta)

{

         

         A[i][j]+=delta;

     

       for(int x = i; x< A.length; x += lowbit(x))

        for(int y = j; y <A[i].length; y += lowbit(y)){

          C[x][y] += delta;

        

        }

     }

 

求子矩阵元素之和∑ a[i][j](i行和前j)的函数为 

    int Sum(int i, int j){

      int result = 0;

      for(int x = i; x > 0; x -= lowbit(x)) {

        for(int y = j; y > 0; y -= lowbit(y)) {

            result += C[x][y];

        }

      }

    return result;

   }

 

[1...x][1...y]=

[x-low(x)...x][y-low[y]...y]+[x-low(x)...x][y-low(y)-low[y-low(y)]...y-low(y)]......

 

 

 

这题是比较经典的二维树状数组,题意是给你个矩阵里面开始全是0,然后给你两种指令:1:‘C x1,y1,x2,y2’就是将左上角为x1,y1,右下角为x2,y2,的这个矩阵内的数字全部翻转,01,10,

2:‘Q x1 y1‘,输出a[x1][y1]的值

 

如果需要对(x1,y1)(x2,y2)区域,即黄色框出的区域,进行翻转的话,只需要对上图中四个绿色的点进行加1操作即可。这样以后求任意一点的当前状态,通过求sum[(1,1)...(x,y)]%2即可,比如下图求点6(x,y)的当前状态:

当然这样做的前提是所有状态只有01,通过求sum的方法并不能求出任意一点翻转了多少次,比如上图中绿色点7右边的点5,计算改点的sum的时候,虽然由于点4和点7都进行加1操作,得出5翻转两次的结论,实际上一次也没有。

 

最后由于存在求和操作,因此对这里的数组进行树状数组化处理,以使得求和变得快速。同时由于使用树状数组,因此更新值的时候,需要把父节点的值也要更新

 

 

 

 

#include<cstdio>

#include<cstring>

 

int ss[1001][1001],n;

 

int lowbit(int x)

{

return x&(-x);

}

 

void modify(int x1,int x2)

{

int i,j;

for(i=x1;i<=n;i+=lowbit(i))

for(j=x2;j<=n;j+=lowbit(j))

ss[i][j]+=1;

}

 

int sum(int x,int y)

{

int res=0,i,j;

for(i=x;i>=1;i-=lowbit(i))

for(j=y;j>=1;j-=lowbit(j))

res+=ss[i][j];

return res;

}

 

int main()

{

int t,time,i,j,x1,x2,y1,y2,res;

char ch;

scanf("%d",&t);

for(i=1;i<=t;i++)

{

memset(ss,0,sizeof(ss));

scanf("%d%d",&n,&time);

for(j=1;j<=time;j++)

{

getchar();

ch=getchar();

if(ch==‘C‘)

{

scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

modify(x1,y1);

modify(x1,y2+1);

modify(x2+1,y1);

modify(x2+1,y2+1);

}

else if(ch==‘Q‘)

{

scanf("%d%d",&x1,&y1);

res=sum(x1,y1);

printf("%d\n",res%2);

}

}

printf("\n");

}

return 1;

}

TreeArray2155