可爱的二维数据结构们

前置知识

相信大家都学过了：

1. 树套树、二维树状数组；
2. 四分树；
3. K-D Tree；

正文

给你一个 \(n\times n\) 二维平面，支持单点修改，矩形查询。这是我们树套树、二维树状数组能解决的，时间复杂度 \(\mathcal{O}(n\log^2n)\)。

那如果我们需要支持区间修改呢？此时不太能树套树，除非修改有一定性质。

此时需要使用四分树。

容易证明四分树单点定位 \(\mathcal{O}(\log n)\)，但是矩形定位 \(\mathcal{O}(n)\)。

其实可以看做 \(n\times n\) 个点的 2D Tree，矩形定位 \(\mathcal{O}(\sqrt{n\times n})=\mathcal{O}(n)\)。

四分树有两种写法，一种是四叉树形式，一种是每次分割矩形的长边的二叉树形式，是差不多的。