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?