首页 > 代码库 > TreeArray1195

TreeArray1195

 

题意:要求设计这样一个数据结构,支持下列操作

 

1.add(x,y,a).对二维数组的第x,y列加上a.

 

2.sum(l,b,r,t).求所有满足l<=x<=r,b<=y<=t,的数组元素的和.

 

显然,二维树状数组满足这些要求.

 

 

 

一维树状数组很容易扩展到二维,在二维情况下:数组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)]......

TreeArray1195