1640.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1640 on 2006-07-21 at 14:49:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;

class D2TreeArray {
private:
	int n, a[N][N];
	int sum(int, int);
public:
	bool make();
	void add(int, int, int);
	int query(int l, int d, int r, int u) { return sum(r, u)-sum(r, d-1)-sum(l-1, u)+sum(l-1, d-1); }
};
bool D2TreeArray::make() {
	if(scanf("%*d %d", &n) == EOF) return false;
	memset(a, 0, sizeof(a)); return true;
}
void D2TreeArray::add(int x, int y, int k) {
	int i, j;
	for(i = x+1; i <= n; i += i&(-i))
		for(j = y+1; j <= n; j += j&(-j))
			a[i-1][j-1] += k;
}
int D2TreeArray::sum(int x, int y) {
	int i, j, s = 0;
	for(i = x+1; i > 0; i -= i&(-i))
		for(j = y+1; j > 0; j -= j&(-j))
			s += a[i-1][j-1];
	return s;
}

D2TreeArray d2ta;

int main()
{
	while(d2ta.make()) {
		while(true) {
			int ito; scanf("%d", &ito);
			if(ito == 1) {
				int x, y, a; scanf("%d %d %d", &x, &y, &a);
				d2ta.add(x, y, a);
			} else if(ito == 2) {
				int l, d, r, u; scanf("%d %d %d %d", &l, &d, &r, &u);
				printf("%d\n", d2ta.query(l, d, r, u));
			} else if(ito == 3) break;
		}
	}
	
	return 0;
}