brdy's blog

How to implement 2D Segment Tree Range Updates/Queries?
By brdy, history, 7 years ago, In English

According to animeshf, it is possible: his comment

But the implementation link he shared is expired so the implementation is gone! I'm confused one how to lazily propagate changes in the second dimension, more specifically how to store the lazy updates in a way so that both operations are logn^2 worst case.

Any ideas here?

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

Comments Comments (5)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Here is a way to support range sum query and range addition update. I don't know of a way to support range set update, however.

https://github.com/bqi343/USACO/blob/master/Storage/(2)%20Data%20Structures/(5)%202D%20BIT%20with%20Range%20Update.cpp

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brdy (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Here

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

    Although the code is quite clean, would you please provide some explanation about it?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Instead of lazily propagating down values he just adds them as he goes down. If a node is not completely within or out of the range he adds the lazy values from min(end,right) to max(start,left) to avoid over-adding. This won't work for max/min though, I'm not sure if there is another idea for those.

      → Reply