gongy's blog

By gongy, history, 3 years ago, In English,

Hello everyone!

My friend and I were discussing range update and range query of maximum in two dimensions and I am not sure how to implement such a data structure. It appears to be much more difficult than range query/update in one dimensions as it is hard to propagate a tree.

Can anyone provide any insight on this?

Thanks in advance

 
 
 
 
  • Vote: I like it
  • +45
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's impossible to achieve log^2 worst case time complexity. But you can use quad tree instead, which gives O(N) per update/query.

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

    ?? But there is 2D segment tree for queries with such complexity... += and sum on range are possible with log^2 complexity.

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

      Can you handle other types of queries apart from submatrix-sum queries (with range updates) using 2D Segment Trees in ? Something like max or min?

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

        Personally I can't even handle += and sums :)

        I just know that it's possible

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

          That's a much too strong statement to be left with positive number of votes and without evidence at the same time.

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

            Comment ratings on Codeforces rarely make any sense

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

            Sum queries can surely be handled with updates in .
            Max/Min seems hard.

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

              I was talking about max/min, though what you are talking about is not what is usually called 2d-queries.

              What you have done allows to perform rectangle queries and updates on 2d-array of size, like, 1000x1000.

              But the more common problem is when you have, like, 105 points in the plane with arbitrary coordinates, each point is assigned with some weight and you are asked to perform two kinds of queries: getting sum of weights of all points belonging to a rectangular region and increasing weights of all points belonging to a rectangular region by some constant.

              This also can be done in per query, but I only know an approach that requires memory and that is completely inefficient. The best choice for such a problem would be using an sqrt-decomposition rather than a log2n approach.

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

                But what exactly is wrong with nested BSTs solution? Its space requirement would be .

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

        Yes max and min functions are also possible.

        Edit: I haven't seen that it's with updates. No 2d segment trees can't handle 2d rectangle updates. As each row update will have different cols ranges so lazy propagation can't be applied.

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

      Add submatrix and query sum of submatrix can be supported using 2D BIT (thus possible using 2D segment tree). But I believe add submatrix and get max on submatrix cannot be done the same way as the 1D case, and quadtree is the best I know for such cases.

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

    But Quad tree is for square grid n*n

    not for n*m

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

      Well, simply view the matrix as max(m,n) * max(m,n) if you want :)

      In fact quadtree is built separately on each dimension, so you don't have to make sure the matrix is square.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi !

Problem Tetris 3D require a 2D segment tree with update and query on range (it is what you need).

It is possible !

We need 2 segment tree (one main and other for lazy propagation) that every node of this segment trees has 2 segment trees; one main and other for lazy propagation.

It has a log^2 worst case time complexity.

See my code for better understanding.

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

    I've inspected your code:

    1. There's no lazy propagation. Lazily building tree is not the thing.
    2. The problem you deal with is specific: it is range max with strictly increasing overwrites. That's the reason your code safely overwrites aggregated values and never has to push delayed operations.
»
12 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Have anyone solved this problem now? Or is there any idea about how to prove the lower bound?