[DataStructure]Quad Tree

QuadTree是一种应用在2D数据当中把空间递归地四等分的数据结构。在图像处理当中有很多的应用，除此之外其在range query当中也可以给我提供帮助。对于给定的Matrix，我们可以递归地将其四等分，如下图所示(picture from StackOverflow)：

QuadTree Node:

我们在这里以Region Sum为例，假设输入Matrix为m * n。首先我们要构建QuadTree，这和给定array建Binary Tree是类似的，Bottom-up建造即可。O(m * n)时间，代码如下：

对于查询来说，分三种情况：

• 区间如果不满足左边界小于等于右边界，上边界小于等于下边界的基本条件，return 0。这是base case
• 如果查询区间和当前区间没有交集，return 0。
• 如果有，递归地查询四个子区间。

代码如下：

时间复杂度的话，取决于查询区间的范围，最好的情况查询区间正好和当前区间重合，O(1)。最坏的情况对于每个分区我们可能要一直查询到底，时间复杂度O(m * n)，比如下图例子：

更新的话，我们只要看更新的元素在四个子节点其中的哪个，然后递归地进行更新即可。时间复杂度O(log(m * n))，这里我们不考虑频繁的区间更新，如果需要支持高频的区间更新的话可以考虑Segment Tree，因为显然Segment Tree的区间更新更有效率。代码如下：



QuadTree所占用的空间为O(m * n)，因为其一定有m * n个叶节点，并且internal节点的数量不会啊超过叶节点的数量。