While solving problem F of 394 div 2 I needed to solve the problem, fill rectangle (a,b) to (c,d) with value V. There are Q queries of this form.
I need to find for each cell, the total value of it i.e. F[i][j] where F is the final array after all the updates are performed.
I extended the simple 1d method. to update range [l, r] set F[l] = F[l] + 1, F[r + 1] = F[r + 1] — 1, and taking cumulative sum.
In 2d, I took two 2d arrays, start[i][j], finish[i][j]
whenever i see a rectangle (a,b) to (c,d), updates are
start[a][b]++
finish[a][d]++
start[c + 1][b]--
finish[c + 1][d]--
Think of this method as when a segment from column b to d starts i.e. at a and when the segment should be removed i.e. at c + 1
Now for each row, I take cumulative sum as in 1d which is take cumulative sum of start[i][j] and subtract finish[i][j] when leaving the cell, also push start[i][j] and finish[i][j] down
This method works, but I have seen other methods while using just one 2d array.
Can anyone explain the method?
P[a][b]++, P[a][d+1]--, P[c+1][b]--, P[c+1][d+1]++;
You can check that the final value of cell (r,c) is sum of values written in the rectangle starting at the upper-left corner of the array and ending at (r,c).
How does the calculation part look like, is it just the old 2d method P[a][b] = P[a — 1][b] + P[a][b — 1] + P[a][b] — P[a — 1][b — 1]
Yes.