POJ 1195 - Mobile phones 二維樹狀數組(單點更新..區間查詢)

            題意:

                    給了一個N*N的矩陣(N<2^10)...初始所有位置都是0...現在有幾種操作:

                              1 x1 y1 x2 y2  : (0<x1<=x2<N && 0<y1<=y2<N ) 輸出(x1,y1)為左下角..(x2,y2)為右上角的子矩陣的所有數之和

                              2 x y d : (0<x,y<N) 在(x,y)處加d

            題解: 

                    so easy了~~裸二維線段樹..和POJ2155不同的是本題是單點更新區間查詢..實際上是一回事...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<time.h>
#define ll long long
#define oo 1000000009
#define MAXN 1030
#define pi acos(-1.0)
#define esp 1e-30
#define MAXD 4
using namespace std;
int N,sum[MAXN][MAXN];
void updateX(int x,int y,int d)
{
       while (x<=N)
       {
             sum[x][y]+=d;
             x+=x&(-x);
       }
} 
void update(int x,int y,int d)
{
       while (y<=N)
       {
             updateX(x,y,d);
             y+=y&(-y);
       }
} 
int queryX(int x,int y)
{
       int ans=0;
       while (x)
       {
             ans+=sum[x][y];
             x-=x&(-x);
       }
       return ans;
}
int query(int x,int y)
{
       int ans=0;
       while (y)
       {
             ans+=queryX(x,y);
             y-=y&(-y);
       }
       return ans;
}
int main()
{
       int tp,x1,y1,x2,y2,x,y,d;
       freopen("input.txt","r",stdin);  freopen("output.txt","w",stdout);  
       scanf("%d%d",&tp,&N);
       memset(sum,0,sizeof(sum));
       while (~scanf("%d",&tp) && tp!=3)
       {
                if (tp==1)
                {
                      scanf("%d%d%d",&x,&y,&d),x++,y++;
                      update(x,y,d);
                }else
                {
                      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                      x2++,y2++;
                      printf("%d\n",query(x2,y2)+query(x1,y1)-query(x2,y1)-query(x1,y2));
                }
       }
       return 0;
}