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<br><b> Q(x1, y1, x2, y2) {x1<=x2 and y1<=y2} = Q'(x2, y2)-Q'(x1, y2)-Q'(x2, y1)+Q'(x1, y1). </b> <br>↵
[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.]↵
<br>↵
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>↵
↵
~~~~~↵
void buildy(int idx, int lx, int rx, int idy, int ly, int ry)↵
{↵
if(ly==ry)↵
{↵
if(lx==rx) segt[idx][idy]=a[idx][idy];↵
else segt[idx][idy]=max(segt[idx*2][idy], segt[idx*2+1][idy]);↵
lzy[idx][idy]=lazy[idx][idy]=0;↵
return;↵
}↵
int mid=(ly+ry)/2;↵
buildy(idx, lx, rx, idy*2, ly, mid);↵
buildy(idx, lx, rx, idy*2+1, mid+1, ry);↵
segt[idx][idy]=max(segt[idx][idy*2], segt[idx][idy*2+1]);↵
lzy[idx][idy]=lazy[idx][idy]=0; ↵
}↵
void buildx(int ind, int l, int r)↵
{↵
if(l!=r)↵
{↵
int mid=(l+r)/2;↵
buildx(ind*2, l, mid);↵
buildx(ind*2+1, mid+1, r);↵
return;↵
}↵
buildy(ind, l, r, 1, 0, m-1);↵
}↵
↵
~~~~~↵
↵
</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>↵
↵
~~~~~↵
↵
void updy(int idx, int lx, int rx, int idy, int ly, int ry, int stx, int endx, int sty, int endy, int val)↵
{↵
lazify(idx, idy, lx, rx, ly, ry);↵
if(ly>=sty && ry<=endy)↵
{↵
if(lx>=stx && rx<=endx)↵
{↵
segt[idx][idy]+=val;↵
if(ly!=ry)↵
{↵
lzy[idx][idy*2]+=val;↵
lzy[idx][idy*2+1]+=val;↵
}↵
if(lx!=rx)↵
{↵
lazy[idx*2][idy]+=val;↵
lazy[idx*2+1][idy]+=val;↵
}↵
}↵
else↵
{↵
segt[idx][idy]=max(segt[idx*2][idy], segt[idx*2+1][idy]);↵
}↵
return;↵
}↵
if(ly>endy || ry<sty) return;↵
int mid=(ly+ry)/2;↵
updy(idx, lx, rx, idy*2, ly, mid, stx, endx, sty, endy, val);↵
updy(idx, lx, rx, idy*2+1, mid+1, ry, stx, endx, sty, endy, val);↵
segt[idx][idy]=max(segt[idx][idy*2], segt[idx][idy*2+1]);↵
}↵
void updx(int ind, int lx, int rx, int stx, int endx, int sty, int endy, int val)↵
{↵
int lazyupd=queryy(ind, 1, lx, rx, 0, m-1, sty, endy);↵
if(lx>endx || rx<stx) return;↵
if(lx>=stx && rx<=endx)↵
{↵
updy(ind, lx, rx, 1, 0, m-1, stx, endx, sty, endy, val);↵
return;↵
}↵
int mid=(lx+rx)/2;↵
updx(ind*2, lx, mid, stx, endx, sty, endy, val);↵
updx(ind*2+1, mid+1, rx, stx, endx, sty, endy, val);↵
updy(ind, lx, rx, 1, 0, m-1, stx, endx, sty, endy, val);↵
return;↵
}↵
↵
~~~~~↵
↵
</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: <br>↵
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>↵
↵
~~~~~↵
lazy[idx*2][idy]+=lazy[idx][idy];↵
lazy[idx*2+1][idy]+=lazy[idx][idy];↵
lazy[idx][idy*2]+=lazy[idx][idy];↵
lazy[idx][idy*2+1]+=lazy[idx][idy];↵
↵
~~~~~↵
↵
</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>↵
↵
~~~~~↵
void lazify(int idx, int idy, int lx, int rx, int ly, int ry)↵
{↵
if(lx!=rx)↵
{↵
lazy[idx*2][idy]+=lazy[idx][idy];↵
lazy[idx*2+1][idy]+=lazy[idx][idy]; ↵
}↵
if(ly!=ry)↵
{↵
lzy[idx][idy*2]+=lazy[idx][idy];↵
lzy[idx][idy*2]+=lzy[idx][idy];↵
lzy[idx][idy*2+1]+=lazy[idx][idy];↵
lzy[idx][idy*2+1]+=lzy[idx][idy];↵
}↵
segt[idx][idy]+=lazy[idx][idy];↵
segt[idx][idy]+=lzy[idx][idy];↵
lzy[idx][idy]=lazy[idx][idy]=0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
Finally I come to queries. We do the junk variable based lazy propogation here too. The rest is pretty trivial.↵
↵
<spoiler>↵
↵
~~~~~↵
↵
int queryy(int idx, int idy, int lx, int rx, int ly, int ry, int sty, int endy)↵
{↵
lazify(idx, idy, lx, rx, ly, ry);↵
if(ly>endy || ry<sty) return 0;↵
if(ly>=sty && ry<=endy)↵
{↵
return segt[idx][idy];↵
}↵
int mid=(ly+ry)/2;↵
return max(queryy(idx, idy*2, lx, rx, ly, mid, sty, endy), queryy(idx, idy*2+1, lx, rx, mid+1, ry, sty, endy)); ↵
}↵
int queryx(int ind, int lx, int rx, int stx, int endx, int sty, int endy)↵
{↵
int lzyupd=queryy(ind, 1, lx, rx, 0, m-1, sty, endy); ↵
if(lx>endx || rx<stx) return 0;↵
if(lx>=stx && rx<=endx)↵
{↵
return queryy(ind, 1, lx, rx, 0, m-1, sty, endy);↵
}↵
int mid=(lx+rx)/2;↵
return max(queryx(ind*2, lx, mid, stx, endx, sty, endy), queryx(ind*2+1, mid+1, rx, stx, endx, sty, endy));↵
}↵
↵
~~~~~↵
</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↵
↵
↵
This was probably because most 2D Data Structure approaches were based on Fixing an Origin, and then handling queries as<br><b> Q(x1, y1, x2, y2) {x1<=x2 and y1<=y2} = Q'(x2, y2)-Q'(x1, y2)-Q'(x2, y1)+Q'(x1, y1). </b> <br>↵
[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.]↵
<br>↵
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>↵
↵
~~~~~↵
void buildy(int idx, int lx, int rx, int idy, int ly, int ry)↵
{↵
if(ly==ry)↵
{↵
if(lx==rx) segt[idx][idy]=a[idx][idy];↵
else segt[idx][idy]=max(segt[idx*2][idy], segt[idx*2+1][idy]);↵
lzy[idx][idy]=lazy[idx][idy]=0;↵
return;↵
}↵
int mid=(ly+ry)/2;↵
buildy(idx, lx, rx, idy*2, ly, mid);↵
buildy(idx, lx, rx, idy*2+1, mid+1, ry);↵
segt[idx][idy]=max(segt[idx][idy*2], segt[idx][idy*2+1]);↵
lzy[idx][idy]=lazy[idx][idy]=0; ↵
}↵
void buildx(int ind, int l, int r)↵
{↵
if(l!=r)↵
{↵
int mid=(l+r)/2;↵
buildx(ind*2, l, mid);↵
buildx(ind*2+1, mid+1, r);↵
return;↵
}↵
buildy(ind, l, r, 1, 0, m-1);↵
}↵
↵
~~~~~↵
↵
</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>↵
↵
~~~~~↵
↵
void updy(int idx, int lx, int rx, int idy, int ly, int ry, int stx, int endx, int sty, int endy, int val)↵
{↵
lazify(idx, idy, lx, rx, ly, ry);↵
if(ly>=sty && ry<=endy)↵
{↵
if(lx>=stx && rx<=endx)↵
{↵
segt[idx][idy]+=val;↵
if(ly!=ry)↵
{↵
lzy[idx][idy*2]+=val;↵
lzy[idx][idy*2+1]+=val;↵
}↵
if(lx!=rx)↵
{↵
lazy[idx*2][idy]+=val;↵
lazy[idx*2+1][idy]+=val;↵
}↵
}↵
else↵
{↵
segt[idx][idy]=max(segt[idx*2][idy], segt[idx*2+1][idy]);↵
}↵
return;↵
}↵
if(ly>endy || ry<sty) return;↵
int mid=(ly+ry)/2;↵
updy(idx, lx, rx, idy*2, ly, mid, stx, endx, sty, endy, val);↵
updy(idx, lx, rx, idy*2+1, mid+1, ry, stx, endx, sty, endy, val);↵
segt[idx][idy]=max(segt[idx][idy*2], segt[idx][idy*2+1]);↵
}↵
void updx(int ind, int lx, int rx, int stx, int endx, int sty, int endy, int val)↵
{↵
int lazyupd=queryy(ind, 1, lx, rx, 0, m-1, sty, endy);↵
if(lx>endx || rx<stx) return;↵
if(lx>=stx && rx<=endx)↵
{↵
updy(ind, lx, rx, 1, 0, m-1, stx, endx, sty, endy, val);↵
return;↵
}↵
int mid=(lx+rx)/2;↵
updx(ind*2, lx, mid, stx, endx, sty, endy, val);↵
updx(ind*2+1, mid+1, rx, stx, endx, sty, endy, val);↵
updy(ind, lx, rx, 1, 0, m-1, stx, endx, sty, endy, val);↵
return;↵
}↵
↵
~~~~~↵
↵
</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: <br>↵
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>↵
↵
~~~~~↵
lazy[idx*2][idy]+=lazy[idx][idy];↵
lazy[idx*2+1][idy]+=lazy[idx][idy];↵
lazy[idx][idy*2]+=lazy[idx][idy];↵
lazy[idx][idy*2+1]+=lazy[idx][idy];↵
↵
~~~~~↵
↵
</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>↵
↵
~~~~~↵
void lazify(int idx, int idy, int lx, int rx, int ly, int ry)↵
{↵
if(lx!=rx)↵
{↵
lazy[idx*2][idy]+=lazy[idx][idy];↵
lazy[idx*2+1][idy]+=lazy[idx][idy]; ↵
}↵
if(ly!=ry)↵
{↵
lzy[idx][idy*2]+=lazy[idx][idy];↵
lzy[idx][idy*2]+=lzy[idx][idy];↵
lzy[idx][idy*2+1]+=lazy[idx][idy];↵
lzy[idx][idy*2+1]+=lzy[idx][idy];↵
}↵
segt[idx][idy]+=lazy[idx][idy];↵
segt[idx][idy]+=lzy[idx][idy];↵
lzy[idx][idy]=lazy[idx][idy]=0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
Finally I come to queries. We do the junk variable based lazy propogation here too. The rest is pretty trivial.↵
↵
<spoiler>↵
↵
~~~~~↵
↵
int queryy(int idx, int idy, int lx, int rx, int ly, int ry, int sty, int endy)↵
{↵
lazify(idx, idy, lx, rx, ly, ry);↵
if(ly>endy || ry<sty) return 0;↵
if(ly>=sty && ry<=endy)↵
{↵
return segt[idx][idy];↵
}↵
int mid=(ly+ry)/2;↵
return max(queryy(idx, idy*2, lx, rx, ly, mid, sty, endy), queryy(idx, idy*2+1, lx, rx, mid+1, ry, sty, endy)); ↵
}↵
int queryx(int ind, int lx, int rx, int stx, int endx, int sty, int endy)↵
{↵
int lzyupd=queryy(ind, 1, lx, rx, 0, m-1, sty, endy); ↵
if(lx>endx || rx<stx) return 0;↵
if(lx>=stx && rx<=endx)↵
{↵
return queryy(ind, 1, lx, rx, 0, m-1, sty, endy);↵
}↵
int mid=(lx+rx)/2;↵
return max(queryx(ind*2, lx, mid, stx, endx, sty, endy), queryx(ind*2+1, mid+1, rx, stx, endx, sty, endy));↵
}↵
↵
~~~~~↵
</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↵
↵
