M.A.H.M.O.O.D's blog

2D-segment trees and quad trees
By M.A.H.M.O.O.D, history, 7 years ago, In English

Good day everyone.

Today I was trying to solve a problem that required 2D segment trees so I tried to learn them. I didn't get enough resources and the ones I got I didn't understand.

I have encountered the word 'quadtree' a lot so I have a couple of questions.

Could somebody tell me the diffrence between quadtrees and 2D-segment trees or are they the same? and could somebody point me to an article the explains 2D-segment trees well enough to be understood by me. Or can someone explain it here please ?

Thank you for reading.

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

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

hello, I can surely help you.

http://codeforces.net/blog/entry/55286

I will explain the quad-cut tree in next tutorial, and also difference b/w these two data structure. Give me some time. :)

Till then, I can tell you that there was one on stackoverflow, which was explaining quad-cut tree. and it's complexity.

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

    Thanks, your video is awesome I understand the concept behind it now.

    btw Can you use lazy propagation on 2D-segment trees ?

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

      Could you please share the link of the problem you were trying to solve? Thanks.

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

        Problem.

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

          I actually solved this in O(n4). 2D prefix sums suffice for a solution in O(n2).

          Lazy propagation cannot be done in 2D. (But you can do 2D rectangle sum updates with BIT).

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

      I will try. Right now I am outside. and Might be busy for next few days as well. I will try my best :) .

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Quad tree is usually not the right answer, it takes O(n log n) worst case (imagine querying the upper most line of length n), 2d seg takes (log^2 n) worst case.

→ Reply