bochet's blog

2D Segment Tree with range multiplication, is it possible?
By bochet, history, 9 years ago, In English

Hi all,

This is my first blog in Codeforces. I met an optimisation problem in my work. The problem can be simplified as this:

we need to perform two operations on a matrix A:

  1. multiply a sub matrix (given xmin, xmax, ymin, ymax) of A by a constant c_i
  2. query the sum of a sub matrix of A

My first idea is to use 2D segment tree with range update because I have seen and solved problems like (1) 2D segment tree for rmq, (2) 1d segment tree with range multiplication. But after spending one day trying to combine 2d segment tree with range multiplication, I found it very difficult (or maybe impossible ?) to do that because the two nodes may intersect, for example in:

will intersect at point (2, 3) and other points, and that makes everything so hard!

I can switch to quadtree to avoid such a problem, but then it means the single operation complexity would go from O(log(W)*log(H)) to O(W+H).

So can you help me with this problem?

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

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

Auto comment: topic has been updated by bochet (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bochet (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As far as i know lazy propagation with range tree is not possible.

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

    thanks, so is there any other solution to solve this problem besides quadtree？

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 8   Vote: I like it +3 Vote: I do not like it

      You can reach to complexity with sqrt decomposition plus segment tree.

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

        As it would be that? Do you have any code?

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      double post

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Actually you can delete comment, can't you?

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

          First time I heard such a thing. How can I do it?

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

            Next to "edit" option, there's also "delete", but only for a while after having posted it.

            → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    since we will multiple each element at most lg 10^18 times so whats to harm to just edit them by hand?

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

      Assume that you are using big numbers or modulos.

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

      constant c_i is double or float

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

        Then we don't need to save more than 18 digits do we?
        if we do then we would need big num which would make the time bad
        i don't think getting modulo in double is a good idea idk

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1d segment tree with range multiplication?

Do you have any tutorials/blogs for this?

I need a working code to understand how to use segment trees that supports range multiplication?

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

    search for Codeforces 138c (Mushroom Gnomes — 2) and its tutorial

    → Reply