程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ1195 Mobile phones 二維樹狀數組的應用

POJ1195 Mobile phones 二維樹狀數組的應用

編輯：C++入門知識

題意：

給你一個s*s的正方形區域，先輸入一個x，若x==0,則再輸入一個s，若x==1,則輸入x,y,a，表示矩陣中(x,y)這點的值加上a，若x==2，輸入l,b,r,t,代表以左上角的點(l,b)右下角的點(r,t),求這一片矩形內的矩陣元素之和，若x==3則結束此次程序

就是最基礎的二維樹狀數組的應用，修改單點的值，並且快速求區間和

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;

int n;

int c[1000 + 35][1000 + 35];

void clear() {
	memset(c,0,sizeof(c));
}

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

void add(int x,int y,int value) {
	int i = y;
	while(x <= n) {
		y = i;
		while(y <= n) {
			c[x][y] += value;
			y += lowbit(y);
		}
		x += lowbit(x);
	}
}

int get_sum(int x,int y) {
	int sum=0,i = y;
	while(x > 0) {
		y = i;
		while(y > 0) {
			sum += c[x][y];
			y -= lowbit(y);
		}
		x -= lowbit(x);
	}
	return sum;
}

int main() {
	int x;
	while(true) {
		scanf(%d,&x);
		if(x == 0) {
			scanf(%d,&n);
			n++;
			clear();
		}
		else if(x == 1) {
			int x,y,a;
			scanf(%d %d %d,&x,&y,&a);
			add(++x,++y,a);//矩陣行列標由0開始要處理掉
		}
		else if(x == 2) {
			int l,b,r,t;
			scanf(%d %d %d %d,&l,&b,&r,&t);
			l++,b++,r++,t++;//處理行列標
			int ans = 0;
			//int a1 = get_sum(r,b-1);
			//int a2 = get_sum(l-1,b-1);
			//int a3 = get_sum(r,t);
			//int a4 = get_sum(l-1,t);
			ans = get_sum(r,t) - get_sum(l-1,t) - get_sum(r,b-1) + get_sum(l-1,b-1);
			printf(%d
,ans);
		}
		else break;
	}
	return 0;
}