2D BIT BIT can be used as a multi-dimensional data structure. Suppose you have a plane with dots (with non-negative coordinates). You make three queries: set dot at (x , y) remove dot from (x , y) count number of dots in rectangle (0 , 0), (x , y) - where (0 , 0) if down-left corner, (x , y) is up-right corner and sides are parallel to x-axis an…

2D BIT.cpp

void update(int x , int y , int val){
	while (x <= max_x){
		updatey(x , y , val); 
		// this function should update array tree[x] 
		x += (x & -x); 
	}
}

void updatey(int x , int y , int val){
	while (y <= max_y){
		tree[x][y] += val;
		y += (y & -y); 
	}
}

in one function
-------------------
void update(int x , int y , int val){
	int y1;
	while (x <= max_x){
		y1 = y;
		while (y1 <= max_y){
			tree[x][y1] += val;
			y1 += (y1 & -y1); 
		}
		x += (x & -x); 
	}
}