bhikkhu's blog

By bhikkhu, history, 8 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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).

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]