BIT Solution for Rectangular Pasture

Problems and Contests
#1

Problem Link

I heard that there is a BIT (Fenwick) solution to this problem, which is not intended, but easier than 2D prefix sums. Does anyone know how it works? Where can I find an implementation of this?

#2

I wouldn’t consider a 2d fenwick tree easier, but anyway, it would look something like

int query(int i, int j) { // sum from [1, 1] to [i, j]
	int ans = 0;
	for (int x = i; x > 0; x -= x & (-x))
		for (int y = j; y > 0; y -= y & (-y))
			ans += bit[x][y];
	return ans;
}
 
void update(int i, int j, int k) { // add k to (i, j)
	for (int x = i; x < N; x += x & (-x))
		for (int y = j; y < N; y += y & (-y))
			bit[x][y] += k;
}

then you can do some PIE to get the sum of a rectangle.

#3

What do you mean do PIE? Why do we need PIE in this case? Also, what is the logic of using Fenwick in this problem, isn’t it kind of useless since we don’t need any updates.

#4

PIE as in

int sum(int x1, int y1, int x2, int y2) {
  return query(x2+1,y2+1) - query(x2+1,y1) - query(x1,y2+1) + query(x1,y1);
}
#5

yea it is

#6

It is essentially just a 2d prefix sums, but instead of prefix sums, we use BIT. Is that what you are saying?

#7

BIT is basically dynamic prefix sums.