danhnguyen0902's blog

By danhnguyen0902, 11 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't think this is possible.

  • »
    »
    11 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    @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 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          my solution uses O(NlgN) memory.

          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    Matrix

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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