Approach to 2D Segment Tree with Lazy Propogation (should allow RMQ?)

Правка en5, от shash42, 2018-02-06 18:32:02

I was going through many online blogs on 2D Subrectangle Queries and Updates using Lazy Propogation. I was surprised to find that Subtrectangle Minimum and Maximum Queries were not possible in sub-linear time.

This was probably because most 2D Data Structure approaches were based on Fixing an Origin, and then handling queries as
Q(x1, y1, x2, y2) {x1<=x2 and y1<=y2} = Q'(x2, y2)-Q'(x1, y2)-Q'(x2, y1)+Q'(x1, y1).
[This example shows Range Sum Query]. This is like basic 2D prefix sums but with segment trees/2D BIT to handle updates.

However, I came up with a different approach. [Please note that there is some bug in the codes right now which is taking too long to debug, so I thought I'd first ask if I'm on the right track here before I spend more time debugging as I've already spent a whole day working on this.]
Since we are maintaining a Segment Tree of Rows where each Segment Tree holds another Segment Tree for columns, I went with the naive approach. Now, a segment tree node with range (x, x, y, y) holds the value at that point (arr[x][y]), not the sum from origin till there.

Spoiler

Updates are basically handled in a normal segment tree fashion. If a node's range is completely within update's target range then we make the update and propogate lazy to ranges within the node's range. To do this we first isolate idx nodes within the update's target x range and then for these nodes we set the idy nodes within update's target y range. Since there will be logarithmic of both, the complexity is logNlogM. The 2 lazy arrays are explained after the update codes.

Spoiler

Finally coming to the lazy part. We have 2 lazy arrays, lazy and lzy. Lazy basically propogates over x coordinates whereas lzy propogates over y coordinates. This is important (and can't be merged into a single 2D array) because of the way I chose to propogate:
Imagine a 2D space of idx, idy coordinates. Let the children of idx be below the node and children of idy be on the left. So now we need to propogate in a way that we compress a rectangle between (0, 0 & idx, idy) towards the origin. So an update needs to go both down and left. If we do this simultaneously in a single 2D array as:

Spoiler

the paths will start crossing creating a mess. For eg, an update could go left then down and down then left and thus double update the same node. To prevent this, we make a rule that an update that has been propogated to the left once cant be propogated down. So updates first go down and then each node they visit propogates them to the left. Thus we need 2 arrays lazy and lzy, values in lzy cant be propogated down where as values in lazy can be propogated leftwards once (then they become part of lzy and thus cant go down) and can be propogated down. Notice how calling querry function in a junk variable lazyupd helps to propogate updates for all nodes we visit (logN for each update on idx).

Spoiler

Finally I come to queries. We do the junk variable based lazy propogation here too. The rest is pretty trivial.

Spoiler

While this code is a little buggy still for some reason (would be great if someone could help me correct it), I want to know if the general idea is correct. This should definitely be better than a quad-tree approach or similar if I am not missing some key point. Please go through the post and let me know of your opinion, if it is correct I will make another blogpost hopefully transforming this post into my first tutorial :D

Теги 2d segment tree, lazy propagation, technique, approach

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский shash42 2018-02-06 18:32:02 11 (published)
en4 Английский shash42 2018-02-06 18:29:22 9 Tiny change: ' y1). </b></br>[This exam' -> ' y1). </b> <br>\n[This exam'
en3 Английский shash42 2018-02-06 18:28:44 170
en2 Английский shash42 2018-02-06 18:24:55 6
en1 Английский shash42 2018-02-06 18:23:37 6745 Initial revision (saved to drafts)