KD-Tree，是用来维护一个空间（其实一般是平面）中的信息的数据结构。
以下就 2D-Tree 进行讨论。（盲猜并不会考 3D 及以上）
思想：将一个大矩形以一种方式划分成若干个小矩形，然后询问时只查询与询问矩形有交的小矩形。
每次轮流砍开 x 坐标和 y 坐标，分成左右点的个数相等的两半。
注意，这里用 nth_element 来搞，$O(n)$ 搞定。
采取以下方式来写：
int mid=(l+r)>>1; sort(lis+l,lis+1+mid,lis+1+r,o==0?cmpX,cmpY);
更新时这么写：
void build(int k,int l,int r,int o) { ist[k]=1; if(l==r){ lx[k]=rx[k]=lis[l]; ly[k]=ry[k]=p[lis[l]]; sum[k]=a[lis[l]]; return; } int mid=(l+r)>>1; nth_element(lis+l,lis+mid,lis+r+1,o==0?cmpX:cmpY); build(k1,l,mid,o^1); build(k2,mid+1,r,o^1); lx[k]=min(lx[k1],lx[k2]); rx[k]=max(rx[k1],rx[k2]); ly[k]=min(ly[k1],ly[k2]); ry[k]=max(ry[k1],ry[k2]); sum[k]=sum[k1]+sum[k2]; }
其中 cmpX，cmpY 分别是以 x 坐标和 y 坐标为关键字比较的函数。
时间复杂度 $O(n \log n)$。（但是，不占主要部分）
询问一个矩形，可以证明至多与 $O(\sqrt{n})$ 个小矩形相交（不会证），于是就 $O(q \sqrt{n})$ 了。
注意每个询问矩形被划分成 $O(\sqrt{n})$ 个区间，可以用来询问/修改。
可以考虑珂朵莉分块数组进行配套，支持 $O(1)$ 单点修改 $O(\sqrt{n})$ 区间询问。
当修改一个矩形区域时，在 KD-Tree 上自上而下进行递归，分 3 种情况：（注意与普通线段树不大一样）
1. 不相交，返回。
2. 完全被包含，递归清除所有儿子的标记，然后打上新标记，返回。
3. 部分相交，下推标记，递归处理。
cmd 证明了步骤 2 中这个递归复杂度是均摊 $O(n \log n)$ 的，没看懂（
这个递归过程如下：
1. 若有标记，则标记擦去，返回。（因为已经保证了有标记的节点子孙均没有标记）
2. 若没标记，则递归玩下去。
询问的话，看情况用线段树还是珂朵莉数组。
第一次拿到了一道黑题的最优解 (＾－＾)V
