brdy's blog

By brdy, history, 5 months ago, In English,

According to rekt_n00b, 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  

»
5 months 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

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Gotem??

»
5 months 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).

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it
  • »
    »
    5 months 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?

    • »
      »
      »
      5 months 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.