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://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(n^{4}). 2D prefix sums suffice for a solution inO(n^{2}).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.