2d array trick

Revision en5, by bhikkhu, 2017-02-02 07:45:08

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?

Tags 2d, array, trick

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English bhikkhu 2017-02-02 07:45:08 2 Tiny change: 'sum as in 2d which is' -> 'sum as in 1d which is'
en4 English bhikkhu 2017-02-02 07:35:23 131
en3 English bhikkhu 2017-02-02 07:34:00 6
en2 English bhikkhu 2017-02-02 07:33:18 8 Tiny change: '] + 1, F[r] = F[r] — ' -> '] + 1, F[r + 1] = F[r + 1] — '
en1 English bhikkhu 2017-02-02 07:32:24 925 Initial revision (published)