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.
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.
Thanks, your video is awesome I understand the concept behind it now.
btw Can you use lazy propagation on 2D-segment trees ?
Could you please share the link of the problem you were trying to solve? Thanks.
Problem.
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).
I will try. Right now I am outside. and Might be busy for next few days as well. I will try my best :) .
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.