二维树状数组学习之二：练习POJ 1195

接前文:二维树状数组学习之一：彻底理解http://128kj.iteye.com/blog/1746732

POJ1195题意：大概题意如下：给出一个n*n的矩阵，初始化为均为0，还有关于这个矩阵的几种操作，操作如下：
命令0：n (给出矩阵的维数)
命令1：(X Y A) 对位于坐标（X Y）的值加A；
命令2：（L B R T）求出位于L<=x<=R，B<=y<=T的子矩阵的值的和；
命令3：退出不做任何操作。


分析如下：典型的二维树状数组，典型的动态操作题目。查询子矩阵(x,y,xx,yy)的元素和，注意一下就可以了:

sum(xx, yy)-sum(x-1, yy)-sum(xx, y-1)+sum(x-1,y-1);



所求的子矩阵和是要包含边界的，所以减去的部分就不能包含边界

样例:

Sample Input

0 4         //命令0
1 1 2 3     //命令1
2 0 0 2 2   //命令2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3           //命令3

Sample Output

3
4

AC过的代码:

import java.util.Scanner;
 public class Main{
  int n;//二维数组的维数n*n
  int[][] C;   //二维树状数组
  
  public Main(){
   }

   private int lowbit(int t){  
       return t&(-t);   
    }  
 
    
    private int Sum(int i, int j){//求子矩阵的和,前i行,前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;
   }

     private void Modify(int i, int j, int delta){//修改二维数组的某一项(i,j)
         
       // A[i][j]+=delta;
     
       for(int x = i; x<=n; x += lowbit(x))
        for(int y = j; y <=n; y += lowbit(y)){
          C[x][y] += delta;
        
        }
     }
   
     public static void  main(String[] args){   
       Main ma=new Main();
        ma.go();
     }

     private void go(){
      int k,a,b,cc,x,y;   
      Scanner in=new Scanner(System.in);
       while(true){
         k=in.nextInt();
         if(k==3) break;
         if(k==0){
             n=in.nextInt();
             C=new int[n+1][n+1];
         }else if(k==1){
             a=in.nextInt();
             b=in.nextInt();
             cc=in.nextInt();
             a++;
             b++;
             Modify(a,b,cc);//命令1
          }else{
             x=in.nextInt();//命令2
             y=in.nextInt();
             a=in.nextInt();
             b=in.nextInt();
             x++;
             y++;
             a++;
             b++;
              //所求的子矩阵和是要包含边界的，所以减去的部分就不能包含边界
             System.out.printf("%d\n",Sum(a,b)+Sum(x-1,y-1)-Sum(a,y-1)-Sum(x-1,b));
          }
       }
     }
 }