2D, dynamic range tree.

RangeTree.cpp

#include <bits/stdc++.h>
using namespace std;

/**
 * 2D, dynamic range tree.
 * Allows for fast, O(lg^2 N) range queries and updates, using O(N + Qlg N) memory.
 * The first dimension must be in the interval [0..sx) passed into the constructor,
 * and the second dimension must be in [0..sy). Update adds n to the point at (x, y),
 * while Query takes the sum of all points with coordinates (x' <= x, y' <= y).
 */ 
class RangeTree {
	int sx, sy;
	map<int, int>* fenwick;
public:
	RangeTree(int sx, int sy) : sx(sx), sy(sy) { fenwick = new map<int, int>[sx + 1]; }
	~RangeTree() { delete[] fenwick; }
	void update(int x, int y, int n) {
		for (int i = x + 1; i <= sx; i += i & -i)
			for (int j = y + 1; j <= sy; j += j & -j)
				fenwick[i][j] += n;
	}
	int query(int x, int y) {
		int result = 0;
		for (int i = x + 1; i; i -= i & -i)
			for (int j = y + 1; j; j -= j & -j)
				result += fenwick[i][j];
		return result;
	}
	int query(int x1, int y1, int x2, int y2) {
		return query(x2, y2) - query(x2, y1-1) - query(x1-1, y2) + query(x1-1, y1-1);
	}
};

int main() {
	RangeTree rt(10, 10);
	rt.update(0, 0, 1);
	rt.update(4, 5, 10);
	rt.update(8, 2, 20);
	cout << rt.query(0, 0) << endl;
	cout << rt.query(5, 4) << endl;
	cout << rt.query(4, 5) << endl;
	cout << rt.query(9, 9) << endl;
	cout << rt.query(9, 2) << endl;
	cout << rt.query(7, 5) << endl;
	cout << rt.query(1, 1, 9, 5) << endl;
	cout << rt.query(1, 1, 9, 3) << endl;
}