程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1195

poj 1195

編輯：C++入門知識

很裸的二維樹狀數組。。

注意下標要加 1

[cpp]
//============================================================================
// Name        : hello.cpp
// Author      : lxw
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include<iostream>
#include<algorithm>
using namespace std;

#define MAXN 1050
#define LL __int64

LL c[MAXN][MAXN];
int N;

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

void update(int x,int y,int v){
    for(int i=x;i<=N+5;i+=lowbit(i)){
        for(int j=y;j<=N+5;j+=lowbit(j)){
            c[i][j]+=v;
        }
    }
}

LL getsum(int x,int y){
    LL sum=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            sum+=c[i][j];
        }
    }
    return sum;
}

int main(){
    //setbuf(stdout,NULL);
    int op,v;
    int x1,y1,x2,y2;
    while(scanf("%d",&op)&&op!=3){
        if(op==0){
            scanf("%d",&N);
            memset(c,0,sizeof(c));
            continue;
        }
        if(op==1){
            scanf("%d%d%d",&x1,&y1,&v);
            update(x1+1,y1+1,v);
        }
        if(op==2){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;y1++;x2++;y2++;
            LL ans=getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
            printf("%I64d\n",ans);
        }
    }
}