poj1195

题意：给定一个矩阵有查询有添加操作。

hit :很明显是二维树状数组（第一道二维fenwick哈）

横向纵向维护两个树状数组所以是二维，详见代码

  1 //二维树状数组

    2 
   #include<cstring>
   

    3 #include<cstdio>
   

    4 #include<algorithm>
   

    5 
   using 
   namespace std;
   

    6 
   const 
   int MAX=
   1024 +
   10;
   

    7 
   int c[MAX][MAX];
   

    8 
   int n;
   

    9 
   int lowbit(
   int x)
   

   10 {
   

   11     
   return x&(-x);
   

   12 }
   

   13 
   void add(
   int x,
   int y,
   int d)
   

   14 {
   

   15     
   for(
   int i=x;i<=n;i+=lowbit(i))
   

   16     {
   

   17         
   for(
   int j=y;j<=n;j+=lowbit(j))
   

   18         {
   

   19             c[i][j]+=d;
   

   20         }
   

   21     }
   

   22 }
   

   23 
   int sum(
   int x,
   int y)
   

   24 {
   

   25     
   int ans=
   0;
   

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

   27     {
   

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

   29         {
   

   30             ans+=c[i][j];
   

   31         }
   

   32     }
   

   33     
   return ans;
   

   34 }
   

   35 
   int main()
   

   36 {
   

   37     
   int s,x,y,a;
   

   38     
   int x1,x2,y2,y1;
   

   39     memset(c,
   0,
   sizeof(c));
   

   40     
   while(scanf(
   "
   %d
   ",&s)&&s!=
   3)
   

   41     {
   

   42         
   if(s==
   0) scanf(
   "
   %d
   ",&n);
   

   43         
   else 
   if(s==
   1)
   

   44         {
   

   45             scanf(
   "
   %d %d %d
   ",&x,&y,&a);
   

   46             add(x+
   1,y+
   1,a);
   

   47         }
   

   48         
   else
   

   49         {
   

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

   51             x1++,x2++,y1++,y2++;
   

   52             
   long 
   long ans=sum(x2,y2)-sum(x1-
   1,y2)-sum(x2,y1-
   1)+sum(x1-
   1,y1-
   1);
   

   53             printf(
   "
   %lld\n
   ",ans);
   

   54         }
   

   55     }
   

   56     
   return 
   0;
   

   57 }