题目传送门
>原文链接<

题解 :

KD-Tree 是一个用于处理K维空间点查询的的数据结构

一般来讲,KD-Tree的常用场景是处理数点问题/近邻点问题。本题就是一道常见的二维平面数点问题。

KD-Tree所依赖的基础数据结构是BST,即二叉搜索树。在某些特殊应用场景下,我们可以用替罪羊树代替普通的BST

KD-Tree

  1. 建树的过程

    只以二维平面为例 :

    首先在第一维的概念下找中间点,在BST上建立一个新节点,储存这个中间点的信息,

    然后分别递归建立第一维被中间点分隔的左右区间,分别给这个新节点当作左右儿子。

    如果你并没有理解这句话,请把“平面上的点”与“BST上的点”这两个概念分开来看,

    中间点和左右区间说的是平面,而新节点与左右儿子说的是BST,它们一一对应。

    每次递归要换维,函数传递参数传递一个typ,递归的时候变成 !typ 就可以了。

    现在到了第一维的左右区间,我们维度换到了第二维,同样找一个中间点,建立新节点,递归左右区间。

    如果你喜欢的话,可以称之为“递归上下区间”。

    换维的话,我们一般利用一个全局变量now,它也方便了我们寻找不同维度中间点时用到的重载的小于号。

    二维坐标信息一般这么写 :

    struct Point {int p[2], v;bool operator < (const Point &a) const { return p[now] == a.p[now] ? p[!now] < a.p[!now] : p[now] < a.p[now];}}a[N];

    找中间点的话,我们一般使用stl的nth_element()函数,它在algorithm库里。

    使用方法是nth_element(a+1, a+mid+1, a+n+1) 对于一个从1开始,长度为n的数组,这时候处在位置a+mid+1上的数字正好是第mid大的。

  2. 插入点

    同样有一个不断换维的过程,我们到一个点的时候,通过与它比较坐标大小来判断往哪个儿子走,一直走到一个没有能走的地方,在这个空节点处新建一个节点,储存我们要插入的节点的信息。

    以本题为例,对于每个节点,我们要储存6个变量

    a[p] // 节点坐标,由于使用nth_element把mid换了位置,而每次的节点编号也恰好是mid,所以的确是a[p]而不是a[别的什么东西]mx[p][0] // 在第1维上,子树的坐标最大值 (子树均包括自己)mx[p][1] // 在第2维上,子树坐标的最大值mn[p][0] // 对应的最小值mn[p][1] // 对应的最小值t[p] // 子树权值和

    插入的时候先n++ 然后把新的第n个点的信息建出来,就是刚刚输入的信息。然后直接在BST里往下走到不能走,直接把最后一个点的某个儿子指向n 即可,具体是哪个儿子要看坐标了。

    由于这么插,有可能一直插出来一条链,BST结构会退化,我们一般采用到某个阈值就暴力O(N)重构整棵树。阈值可以设定成每插入10000个点就重构,也可以设成当最深点的dep大于某个值就重构。

    当然,你也可以采用替罪羊的重构方法, 相当于把BST替换成替罪羊。

  3. 查询

    像线段树那样在整棵树上查询你要的区间,如果查询区间完全包含这个点的子树坐标区间,就返回这个点的权值和,否则看一下这个BST上的点是否在查询区间里,如果是就加上,再加上递归左右儿子的权值和,返回。

    这个过程和线段树递归左右区间异曲同工。

  4. 关于邻近点,与本题无关,不在这里讲。

代码:

#include <cctype>#include <cstdio>#include <algorithm>using namespace std;#define ls ch[p][0]#define rs ch[p][1]#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000],*p1,*p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc(); return x;}const int N = 210000;int root, now;int ch[N][2], mx[N][2], mn[N][2], t[N];struct Point { int p[2], v; bool operator < (const Point &a) const { return p[now] == a.p[now] ? p[!now] < a.p[!now] : p[now] < a.p[now]; }}a[N];inline void up(int p, int x) { mx[p][0] = max(mx[p][0], mx[x][0]), mn[p][0] = min(mn[p][0], mn[x][0]), mx[p][1] = max(mx[p][1], mx[x][1]), mn[p][1] = min(mn[p][1], mn[x][1]), t[p] += t[x];}void insert(int x) { int p = root; mx[x][0] = mn[x][0] = a[x].p[0], mx[x][1] = mn[x][1] = a[x].p[1]; t[x] = a[x].v; if(!p) return root = x, void(); now = 0; while(1) { up(p, x); if(a[x] < a[p]) if(ls) p = ls; else return ls = x, void(); else if(rs) p = rs; else return rs = x, void(); now ^= 1; }}int build(int l, int r, int typ) { int mid = (l+r) >> 1; now = typ; nth_element(a+l, a+mid, a+r+1); mx[mid][0] = mn[mid][0] = a[mid].p[0], mx[mid][1] = mn[mid][1] = a[mid].p[1]; t[mid] = a[mid].v; if(l < mid) up(mid, ch[mid][0] = build(l, mid-1, !typ)); else ch[mid][0] = 0; if(r > mid) up(mid, ch[mid][1] = build(mid+1, r, !typ)); else ch[mid][1] = 0; return mid;}int query(int x1, int y1, int x2, int y2, int p) { if(mn[p][0] >= x1 && mx[p][0] <= x2 && mn[p][1] >= y1 && mx[p][1] <= y2) return t[p]; int ret = 0; if(a[p].p[0] <= x2 && a[p].p[0] >= x1 && a[p].p[1] <= y2 && a[p].p[1] >= y1) ret += a[p].v; if(ls && mn[ls][0] <= x2 && mx[ls][0] >= x1 && mn[ls][1] <= y2 && mx[ls][1] >= y1) ret += query(x1, y1, x2, y2, ls); if(rs && mn[rs][0] <= x2 && mx[rs][0] >= x1 && mn[rs][1] <= y2 && mx[rs][1] >= y1) ret += query(x1, y1, x2, y2, rs); return ret ;}signed main() { rd(), rd(); int opt, n = 0, ans = 0; while(1) { opt = rd(); if(opt == 3) break; if(opt == 1) { n ++ ; a[n].p[0] = rd(), a[n].p[1] = rd(), a[n].v = rd(); insert(n); if(n%10000 == 0) root = build(1, n, 0); } if(opt == 2) { int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd(); printf("%d\n", ans = query(x1, y1, x2, y2, root)); } }}