2Dbit.cpp

// 1-indexed
template<class T>
class BIT_2D {
	T bit[512 + 1][512 + 1];
	int h, w;

public:
	BIT_2D() {}

	BIT_2D(int H, int W) {
		clear(H, W);
	}

	void clear(int H, int W) {
		h = H;
		w = W;
		memset(bit, 0, sizeof(bit));
	}

	T sum(int i, int j) {
		T s = 0;
		while (i > 0) {
			int _j = j;
			while (_j > 0) {
				s += bit[i][_j];
				_j -= _j & -_j;
			}
			i -= i & -i;
		}
		return s;
	}

	void add(int i, int j, T x) {
		while (i <= h) {
			int _j = j;
			while (_j <= w) {
				bit[i][_j] += x;
				_j += _j & -_j;
			}
			i += i & -i;
		}
	}

};