Блог пользователя M.A.H.M.O.O.D

Автор M.A.H.M.O.O.D, история, 7 лет назад, По-английски

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.

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

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

hello, I can surely help you.

http://mirror.codeforces.com/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.

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

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.