POJ 1195 Mobile phones（二维树状数组）

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 4123 ;
int tree[1100][1100] ;
int n ;

int lowbit(int i)
{
    return i & (-i) ;
}

void update(int i,int j,int k)
{
    while(i <= n)
    {
        int temp = j ;
        while(temp <= n)
        {
            tree[i][temp] += k ;
            temp += lowbit(temp) ;
        }
        i += lowbit(i) ;
    }
}

int sum(int i,int j)
{
    int sum1 = 0;
    while(i > 0)
    {
        int temp = j ;
        while(temp > 0)
        {
            sum1 += tree[i][temp] ;
            temp -= lowbit(temp) ;
        }
        i -= lowbit(i) ;
    }
    return sum1 ;
}

int main()
{
    int n1 ;
    int l,b,r,t ;
    memset(tree,0,sizeof(tree)) ;
    while(scanf("%d",&n1) && n1 < 3)
    {
        if(n1 == 0)
            scanf("%d",&n) ;
        else if(n1 == 1)
        {
            scanf("%d %d %d",&l,&b,&r) ;
            l++;
            b++ ;
            update(l,b,r) ;
        }
        else if(n1 == 2)
        {
            scanf("%d %d %d %d",&l,&b,&r,&t) ;
            l++ ;
            b++ ;
            r++ ;
            t++ ;
            int s = sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1) ;
            printf("%d\n",s) ;
        }
    }
    return 0;
}