Блог пользователя danhnguyen0902

Автор danhnguyen0902, 11 лет назад, По-английски

Could anyone please tell me how we can perform the Lazy Propagation technique on the 2D Segment Tree? Suppose we're solving this problem: http://www.spoj.com/problems/MATSUM/ with an additional operation:

"SET x1 y1 x2 y2 num" — Find the rectangle from (x1, y1) to (x2, y2) and set all of its cells' values to num.

I think it would be timeout if we don't use the Lazy Propagation technique here.

Thank you so much in advance!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I don't think this is possible.

  • »
    »
    11 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          my solution uses O(NlgN) memory.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    Matrix

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      just 2D RSQ:
      1. Add(x1, y1, x2, y2, 1)
      2. ValueAt(x,y) % 2

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Search for Quadtree

http://www.eecs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

if you can do a normal segtree you can do the Quadtree.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

i think it can be solved using BIT (binary indexed trees) if u know them memory O(N^2) and query O(logN*logN) update O(logn*logN)

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    If you "think", please think more, invent a solution and explain it to everybody.

    BTW, I don't know how to solve this problem using BIT even in 1D-case (and I have some arguments for that it's impossible).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have a solution using BIT 2D (as IOIer described) and got AC in a problem. It is really nice.

      I will solve 1D problem: Assume that we have an array a[1..n], execute following operators:

      • 1 k x: Increase a[1..k] with x

      • 2 k: Get sum a[1..k]

      Let A and B are Fenwick trees, we will now solve this problem.

      In first operator, increase A[k] by kx, increase B[k+1] by x.

      In second operator, we output Sum A[1..k] + k*Sum B[k+1..n].

      Did you understand? Use this approach to solve 2D problem, you will be interested.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        thnx for explaining to him . BTW i have solved many problems of this kind on spoj using BIT

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Oh no, I don't have any difficulties with the original problem from SPOJ.

          This post is about the extended version of that problem (why didn't both of you read it?!), and I clearly understood that you don't know how to solve it using BIT or something else (at least, in better time than with a quadtree).

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Did you realize that we are talking about "extended problem"? I didn't talk about "original problem". Read my comment again.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

              Oh, I have problems with reading too :(. I really thought that the original problem asks to be able to add on a rectangle, not to change a single element, and get the sum.

              But topic author wants to set all the elements on a rectangle to a single value. That's what I was talking about.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится

                Shame on me. Now I realized my reading problem was same to you :)) IOIer's first comment made me thought in wrong way.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            what a shame i misunderstood the post i am really sorry for that !