2D Segment Tree - Codeforces

13 лет назад, скрыть # ^ |

← 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.

→ Ответить

13 лет назад, скрыть # ^ |

← 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!

→ Ответить

13 лет назад, скрыть # ^ |

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.

→ Ответить

cerealguy

13 лет назад, скрыть # ^ |

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

→ Ответить

13 лет назад, скрыть # ^ |

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

→ Ответить

13 лет назад, скрыть # ^ |

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

→ Ответить

13 лет назад, скрыть # ^ |

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).

→ Ответить

__builtin__wolfy

12 лет назад, скрыть # ^ |

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.

→ Ответить

13 лет назад, скрыть # ^ |

← 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!

→ Ответить

13 лет назад, скрыть # ^ |

← 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.

→ Ответить

13 лет назад, скрыть # ^ |

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?

→ Ответить

13 лет назад, скрыть # ^ |

my solution uses O(NlgN) memory.

→ Ответить

13 лет назад, скрыть # ^ |

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?

→ Ответить

13 лет назад, скрыть # ^ |

follow link RSQ in the message above.

→ Ответить

13 лет назад, скрыть # ^ |

← Rev. 3 →

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

Matrix

→ Ответить

sparik

13 лет назад, скрыть # ^ |

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.

→ Ответить