I was researching about 2d (multi-dimensional) segment trees. Firstly, I've looked PrinceOfPersia's tutorial, but there wasn't much about 2d segment trees; that's why I've researched a little bit and found this blog.
Even though, PrinceOfPersia's tutorial doesn't tell much about 2d segment tree, it says that every node in main segment tree is also a segment tree. On contrary, other blog describes a totally different idea.
Can someone explain me (or point out a website that explains it) the idea represented in PrinceOfPersia's tutorial and compare (complexity, usages etc.) these two different approaches? Also, it looks like range update with lazy propagation would work with a quad tree. Is lazy propagation possible in other one?
UPD: Thank you really much for good answers! They're really useful.
Full text and comments »