2D Segment Tree - Codeforces

11 years ago, # ^ |

← Rev. 4 →

Why? Can't we calculate the sum in 2D segment tree as usual and store in each rectangle a lazy update which we will process every time we move down? I believe this should work or am I missing something here:

update(segm, rect, value)
{
    if (segm is fully inside rect)
    {
        segm.upd = value;
        segm.sum = segm.size * segm.upd;
        return;
    }
    if (segm.upd != NULL)
    {
        segm.child.upd = segm.upd;
        segm.child.sum = segm.child.size * segm.child.upd;
        segm.upd = NULL;
    }
    update(segm.child, rect, value); //For those childs that share something with rect
    segm.sum = sum(segm.child.sum);
}

find(segm, rect)
{
    if (segm is fully inside rect)
    {
        return segm.sum;
    }
    if (segm.upd != NULL)
    {
        segm.child.upd = segm.upd;
        segm.child.sum = segm.child.size * segm.child.upd;
        segm.upd = NULL;
    }
    return sum(find(segm.child, rect)); //For those childs that share something with rect
}

Comments: segm is the current element of segment tree, rect is the rectangle we're looking for, value is the value we want to set. Inside segm — upd is our lazy promise that all elements below are equal to it, sum is the current sum of elements, child is 4 children (at most) of the current segment, size is the number of elements in the segment. When I write child I mean do it for all (bound by comment condition) four children. And this implementation is for 2D segment tree not for a segment tree of segment trees.

→ Reply

11 years ago, # ^ |

← Rev. 2 →

Wow, that's exactly what I'm looking for. Thank you so much @eduardische! I know that you divide the matrix into 4 parts, then you build a 2D Segment Tree for all of them, and keep doing it recursively. Can we implement the tree by using only 1D arrays?

I also heard of another approach to implement a 2D Segment Tree for the MATSUM problem: we first build N segment trees for every row, then we build N segment tree for every column. Can we use the Lazy Propagation technique here for this approach? And also, can we implement the tree by using only 1D arrays?

I'm just trying to learn how to implement a 2D Segment Tree in many ways, and I'm trying to do it the best for each way.

Thank you very much again @eduardische!

→ Reply

11 years ago, # ^ |

First of all, you are perfectly fine with 1D arrays — store all segments in one array and just use indexes as references to where the children are. So, for 1D segment tree covering area of N, there are less than 2*N segments, and for 2D segment tree covering area of N*N, there are less than 4*N*N segments; so you should suffice with 1D arrays of that size.

As for segment tree of segment trees I don't really have much experience with them at all, so it's best that I don't comment on that.

→ Reply

cerealguy

11 years ago, # ^ |

You are talking about quad tree which has O(N) complexity per operation.

→ Reply

11 years ago, # ^ |

OK, thanks a lot. Didn't realize that.

→ Reply

11 years ago, # ^ |

I'm really confused now. Could you guys please make it clear to me?

→ Reply

11 years ago, # ^ |

Since the cost of updating and getting data in quad tree is O(N) (imagine a long 1xN rectangle — we would have to split it in small 1x1 pieces in quad tree), it's no longer O(queries * log N), it's O(queries * N).

→ Reply

__builtin__wolfy

10 years ago, # ^ |

Why would a long strip make the quadtree do more work? We'll be splitting into two halves, that's still logarithmic. Could you please give an example? Thanks.

→ Reply

11 years ago, # ^ |

← Rev. 3 →

@cerealguy: Thank you for your response. I have another question: is it possible to use a 2D Segment Tree to solve this problem: http://www.spoj.com/problems/LIS2/ ? I only know to implement a 2D Segment Tree by using a matrix M x N. In LIS2 problem, the matrix's size could be up to 10^5 x 10^5, which is too large. Do you have any idea?

Thank you again!

→ Reply

11 years ago, # ^ |

← Rev. 4 →

for problem MATSUM you don't need an segment tree. use 2d RSQ. Operation "SET x y num" replace by AddAt(x, y, num — GetValue(x, y)).
for problem LIS2 you don't need lazy propagation. use one segment tree by X where in each cell store RMQ by Y. We can solve it offline, so you know all queries before. Use one "coordinate compression" by X, and MaxX * 2 "coordinate compression**s**" by Y for each inner RMQ. Total length of inner RMQ's will be O(MaxX * log(MaxX)).
note: "Range Sum Query (RSQ)" and "Range Maximum Query (RMQ)" the same. the only difference is operation max(a, b) instead of +.
upd: algorithm for LIS2: for i to n do SetValueAt(p[i].x, p[i].y, MaxAt(0 < x < p[i].x, 0 < y < p[i].y) + 1);
upd2: i can't find even russian statement for this problem, but my solition was similar.

→ Reply

11 years ago, # ^ |

Thank you very much Alias! I really appreciate your help! So you're saying that we need at least O(NlgN) memory for the problem LIS2, aren't you?

→ Reply

11 years ago, # ^ |

my solution uses O(NlgN) memory.

→ Reply

11 years ago, # ^ |

Please correct me if I'm wrong! I think that RMQ (or RSQ) is one kind of the problems where we need to answer some given queries. I don't think it is a data structure. What data structure are you using to solve the RMQ (RSQ) problem exactly?

→ Reply

11 years ago, # ^ |

follow link RSQ in the message above.

→ Reply

11 years ago, # ^ |

← Rev. 3 →

I just found out a problem that might need a 2D Segment Tree + Lazy Propagation (I guess):

Matrix

→ Reply

sparik

11 years ago, # ^ |

It doesn't need lazy propagation. Just set or unset the 'update' flag on the needed elements of the segment tree(to cover the rectangle). For query, you must calculate how many times you encounter 'update' flag on its way, if the count is odd then it's 1, otherwise it's 0.

→ Reply