替罪羊树与 KDTree

Arahc 11.0
  2021-11-25 08:00 2021-11-25 08:00 创建   2023-03-18 13:27:58 2023-03-18 13:27:58 更新      4.9k 字  23 分钟  

前言

替罪羊树是一种平衡树。对于平衡树的二叉搜索树性质，已经在这个博客比较详细地提到过了。那篇博客内，详细讲了的平衡树是 Splay。注意到 Splay 维护平衡的时候会直接通过旋转改变树的结构，在写平衡树套什么东西的时候，Splay 维护起来可能会有写吃力。因此这里重点写一下替罪羊树。

KD-Tree 和替罪羊树维护树平衡的方法一样，因此也可以提出来讲讲。

其实重点是 KDT 不是替罪羊。

替罪羊树

平衡树的插入，删除等操作基本都是一致的，重要的是如何维护树的平衡。例如给出一个不太平衡的树：

pic-1

虽然单次查询不至于退化成线性，但是相比于正常情况的 log⁡\log 也够慢了。考虑不平衡的两个典型，就是 1010 和 6464 的两个子树。

替罪羊树的思想很简单，现在既然这两个地方不平衡，那我直接把这两个子树重建一下就可以了。

pic-2

平衡多了。但是众所周知，我不能每次修改一下就要全部重新把不平衡的地方重建。为了保证复杂度，应该需要衡量一个平衡因子 α\alpha。若一个点的左右子树中，较大的子树大小占比达到了 α\alpha，就需要给子树重构。控制合适的 α\alpha 就可以控制替罪羊树的复杂度和常数。

一般来说 α∈[0.65,0.85]\alpha\in[0.65,0.85]。显然不能直接取 0.50.5。因为重构的复杂度是不可忽略的。如果有一点点不平衡就重构，虽然树会很平衡，但是多次重构会使其复杂度仍然接近 n2n^2。

具体的重构实现，可以先把要重构的子树“拍扁”，即按照中序遍历得到对应的序列，然后对于这个序列重新构建子树即可。每次重新构建的时候，应该以中位数对应的节点当作根节点，因为前面是在替罪羊树上中序遍历得到的序列，已经有序了，直接取中间位置就是中位数。

和 Splay 不同的地方还有替罪羊的删除操作。替罪羊树并不能很好地直接删除，因此通常以打标记的方法，如果这个数字被删掉了（出现次数为零），在下一次重构的时候碰到这个点就不管它了。如果写的简单一点也可以直接忽视删除操作，保留原节点，大部分情况都不会被卡。

具体细节可以参考如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
struct SheepTree{
    int root,tot,tmp;
    int pb[max_n]; // 记录拍扁时的中序遍历数组
    SheepTree(){root=tot=tmp=0;}
    const double alpha=0.75;
    struct dot{
        int ls,rs,sz,cnt,sd,sm,val; // 左右儿子、sz、出现次数、sd、sm、维护的值
        dot(){ls=rs=sz=cnt=sd=sm=val=0;}
    }a[max_n];
    #define ls(x) (a[x].ls)
    #define rs(x) (a[x].rs)

    inline void resize(int &x){
        a[x].sz=a[ls(x)].sz+a[rs(x)].sz+(bool)(a[x].cnt); // sz 去掉删掉的点的子树大小
        a[x].sd=a[ls(x)].sd+a[rs(x)].sd+1; // 直接统计节点数的子树大小（数重复出现算一次）
        a[x].sm=a[ls(x)].sm+a[rs(x)].sm+a[x].cnt; // 统计子树对应了实际上的多少个数（重复出现算多次）
    }
    inline bool regain(int &x){ // 判断需不需要重构
        if(!a[x].sm) return 0; // 被删掉了
        return (alpha*a[x].sd<=max(a[ls(x)].sd,a[rs(x)].sd) || alpha*a[x].sd>=a[x].sz);// 子树不平衡，或者删掉了比较多的点影响平衡
    }
    inline void get(int x){ // 中序遍历得到拍扁序列
        if(ls(x)) get(ls(x));
        if(a[x].cnt) pb[++tmp]=x;
        if(rs(x)) get(rs(x));
    }
    inline int build(int l,int r){ // 建树（重构）
        if(l==r){
            ls(pb[l])=rs(pb[l])=0;
            resize(pb[l]);
            return pb[l];
        }
        int mid=(l+r)>>1; // 取中间位置对应的节点，重造
        ls(pb[mid])=rs(pb[mid])=0;
        if(l<=mid-1) ls(pb[mid])=build(l,mid-1); // 读取左右儿子关系
        if(r>=mid+1) rs(pb[mid])=build(mid+1,r);
        resize(pb[mid]);
        return pb[mid]; // 返回当前子树的根节点
    }
    inline void rebuild(int &x){ // 重构树的全流程
        tmp=0;
        get(x); // 中序遍历
        x=build(1,tmp); // 重构这个点的子树
    }
    inline void pushup(int &x){ // 更新节点
        resize(x); // 更新大小等信息
        if(regain(x)) rebuild(x); // 如果需要则重构
    }
    // 剩下的都是板子了
    inline void insert(int &x,int val){
        if(!x){
            x=++tot;
            a[x].val=val,a[x].cnt=1;
            resize(x);
            return;
        }
        if(val==a[x].val) ++a[x].cnt;
        else if(val<a[x].val) insert(ls(x),val);
        else insert(rs(x),val);
        pushup(x);
    }
    inline void delet(int &x,int val){
        if(a[x].val==val) --a[x].cnt;
        else if(val<a[x].val) delet(ls(x),val);
        else delet(rs(x),val);
        pushup(x);
    }
    inline int rank(int &x,int val){
        if(!x) return 1;
        if(val==a[x].val) return a[ls(x)].sm+1;
        else if(val<a[x].val) return rank(ls(x),val);
        else return a[ls(x)].sm+a[x].cnt+rank(rs(x),val);
    }
    inline int kth(int &x,int k){
        if(!x) return -1;
        if(k>a[ls(x)].sm && k<=a[ls(x)].sm+a[x].cnt) return a[x].val;
        else if(k<=a[ls(x)].sm) return kth(ls(x),k);
        else return kth(rs(x),k-a[ls(x)].sm-a[x].cnt);
    }
    inline int pre(int val){
        return kth(root,rank(root,val)-1);
    }
    inline int suf(int val){
        return kth(root,rank(root,val+1));
    }
}shp;

KDTree

建树

KD-Tree 是一个优雅的暴力，复杂度相对可观，但是比较裸的 KD-Tree 容易被卡常。来看一下这样一个题目：

在线地支持两个在平面直角坐标系上的操作：插入一个坐标为 (x,y)(x,y)，权为 ww 的点。矩形查点权和。

n,m≤2×105n,m\leq 2\times10^5，空间限制 20MB。

强制在线卡掉 CDQ，空间限制卡掉树套树。因此我们就需要一个更加优秀的数据结构，可以很好地处理这个问题。KD-Tree 就是一个不错的选择。我们知道平衡树可以做到在一维（序列）的空间上对点进行很多高级的操作，KD-Tree 就是针对 K 维空间进行的，以二维为例子：

pic-3

如果是在一个一维序列上，我们就会遵循 BST 的性质，每次取当前区间的中位数作为根，然后递归地建树。这样建出来的树一定具有 SBT 性质，随后怎么在加点删点时维护平衡就是它自己的事情了。

如果能找到一个标准，使得平面上的点也能建在一个树上，然后尽可能地满足 SBT 性质，那么复杂度就是接近 log⁡\log 级别的。

KD-Tree 并不把事情搞的很复杂，每次我们只需要选择一个维度，然后在当前区间内找到中位数位置划分即可。当然每次选择维度不宜都是同一个，不然非常容易退化，常见的方法是交替选维度。

例如以 xx 为标准，选择 DD：

pic-3

然后换一个维度，各找中位数。注意到 B,GB,G 在一个线上，为了方便随便选一个。假设选的是 B,FB,F：

pic-5

如此类推划分：

pic-6

然后按照划分的顺序，假设对于 xx 为标准的时候，左侧为左子树，yy 时上面为左子树，则有这样一个树：

pic-7

我们发现这个树看起来挺平衡的，那就可以根据这个关系来建树就行，控制了随机数据下在树上进行的操作复杂度约为 log⁡\log 级。

重构

这样就出现了一个问题，因为加点的时候一定是加在一个叶子上的，如果我一直往一个区域加一堆点，这个子树的根就不一定是原来的中位数了。然后加着加着这个树就不平衡了，复杂度就退化了。

只需要和替罪羊树一样，搞上一个平衡因子，如果不平衡就拆下来重构。复杂度还是可以稳定在 log⁡\log。

然后到这里上面那个例题就可以做出来了，我们再维护一下一个点子树内的点权和，这个点本身的点权，和子数内所有点构成的最大矩形。询问的时候，如果询问矩形和这个点涵盖的矩形相离，不会造成贡献，如果询问区间包含了这个点涵盖的矩形，则直接返回这个点的子树点权和。

实测最慢的点不超过 2s。事实上，交替选点的复杂度一般视为单次树上操作 n\sqrt n 级别的。

估价

假设把求矩形内点权和，改成查询离一个点的曼哈顿距离最近的点的距离。

我们发现上面的划分方法有一个很大的弊端，就是有可能一个点和另一个点很近，但是在树上并不出在相邻的位置。举个例子，上面那个划分的图，EE 最近的点是 FF，但是 E,FE,F 不相邻。

因此每次询问的时候，就只能暴力跑一遍整个树吗？那我还建这个树干嘛。因此需要考虑怎么进行优化。

如果当前我找到的这个点，它的能涵盖到的矩形，距离询问点的距离还大于等于当前找到的最优答案，那还要往这个点的子树找干什么。

这样的看起来显然的优化实际上可以让复杂度变得非常优秀。确定好一个合适的搜索顺序后，基本可以看为也是根号级别的。这就是 KD-Tree 的估价。这里给出一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int check(int x,int i){ // 估价函数
    if(!x) return inf; // 不存在这个点，显然不能往这里搜
    return max(a[x].l.x-d[i].x,0)+max(d[i].x-a[x].r.x,0)+max(a[x].l.y-d[i].y,0)+max(d[i].y-a[x].r.y,0); // 点到矩形曼哈顿距离最小值
}
inline void query(int x,int id){
    if(a[x].id!=id) // 查寻点和我现在的点不同，更新答案
        ans=min(ans,abs(a[x].x.x-d[id].x)+abs(a[x].x.y-d[id].y));
    int al=check(ls(x),id),ar=check(rs(x),id); // 计算左右子树估价
    if(al<ar){ // 哪个子树更近，先走哪个，使得较优的答案更早算出来，减枝更多
        if(al<ans) query(ls(x),id); // 如果到矩形的距离都比当前的最有答案大，别走
        if(ar<ans) query(rs(x),id);
    }
    else{
        if(ar<ans) query(rs(x),id);
        if(al<ans) query(ls(x),id);
    }
}

例题

BZOJ3489 A simple rmq problem

给定一个序列，在线处理若干询问，每次询问查询区间内只出现一次的数的最大值。

n,m,ai≤2×105n,m,a_i\leq 2\times 10^5。

题解

先求出每个数字上一次出现的位置和后一次出现的位置，问题转化为找到最大的一个数，使得其上一次出现位置在左端点前，下一次出现位置在右端点后。那么不妨以这个点的位置、这个数上次出现位置、这个数字下一次出现位置三个维度为坐标，值为点权，建立一个 3D-Tree。每次查询的时候在 3D-Tree 上找到符合条件的点的点权最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
const int max_n=300005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,m,a[max_n];

struct point{
	int x,y,z,val;
	point(){x=y=z=val=0;}
}pos[max_n];
inline point makep(int a,int b,int c,int d){
	point res;
	res.x=a,res.y=b,res.z=c,res.val=d;
	return res;
}

int cmpt=0;
inline bool cmp(point i,point j){
	if(cmpt==0) return i.x<j.x;
	if(cmpt==1) return i.y<j.y;
	return i.z<j.z;
}

struct KD_Tree{
	const double alpha=0.65;
	int root,tot,ans;
	KD_Tree(){root=tot=ans=0;}
	struct dot{
		point x,l,r;
		int ls,rs,sz,tp,mx;
		dot(){ls=rs=sz=tp=mx=0;}
	}a[max_n];
	#define ls(x) (a[x].ls)
	#define rs(x) (a[x].rs)
	#define nx(i) ((i+1)%3)

	inline void pushup(int x){
		a[x].l=a[x].r=a[x].x,a[x].mx=a[x].x.val;
		a[x].sz=a[ls(x)].sz+a[rs(x)].sz+1;
		if(ls(x)){
			a[x].mx=max(a[x].mx,a[ls(x)].mx);
			a[x].l.x=min(a[x].l.x,a[ls(x)].l.x),a[x].r.x=max(a[x].r.x,a[ls(x)].r.x);
			a[x].l.y=min(a[x].l.y,a[ls(x)].l.y),a[x].r.y=max(a[x].r.y,a[ls(x)].r.y);
			a[x].l.z=min(a[x].l.z,a[ls(x)].l.z),a[x].r.z=max(a[x].r.z,a[ls(x)].r.z);
		}
		if(rs(x)){
			a[x].mx=max(a[x].mx,a[rs(x)].mx);
			a[x].l.x=min(a[x].l.x,a[rs(x)].l.x),a[x].r.x=max(a[x].r.x,a[rs(x)].r.x);
			a[x].l.y=min(a[x].l.y,a[rs(x)].l.y),a[x].r.y=max(a[x].r.y,a[rs(x)].r.y);
			a[x].l.z=min(a[x].l.z,a[rs(x)].l.z),a[x].r.z=max(a[x].r.z,a[rs(x)].r.z);
		}
	}
	inline int build(int l,int r,int t){
		int x=++tot,mid=(l+r)>>1;
		cmpt=t,
		nth_element(pos+l,pos+mid,pos+r+1,cmp);
		a[x].tp=t,a[x].x=pos[mid],ls(x)=rs(x)=0;
		if(l<mid) ls(x)=build(l,mid-1,(t+1)%3);
		if(r>mid) rs(x)=build(mid+1,r,(t+1)%3);
		pushup(x);
		return x;
	}
	inline bool check(dot x,int l,int r){
		if(x.r.x<l || x.l.x>r || x.l.y>=l || x.r.z<=r) return 1;
		return 0;
	}
	inline void ask(int x,int l,int r){
		if(!x || a[x].mx<=ans || check(a[x],l,r)) return;
		if(a[x].x.x>=l && a[x].x.x<=r && a[x].x.y<l && a[x].x.z>r)
			ans=max(ans,a[x].x.val);
		ask(ls(x),l,r),ask(rs(x),l,r);
	}
	inline int query(int l,int r){
		ans=0;
		ask(root,l,r);
		return ans;
	}
}kdt;

int pre[max_n],suf[max_n],lst[max_n];

inline int Min(int x,int y,int k){
	return min((x+k)%n+1,(y+k)%n+1);
}
inline int Max(int x,int y,int k){
	return max((x+k)%n+1,(y+k)%n+1);
}

signed main(){
//	freopen(".in","r",stdin),
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(register int i=1;i<=n;++i){
		a[i]=read();
		pre[i]=lst[a[i]],
		lst[a[i]]=i;
	}
	for(register int i=1;i<=n;++i)
		lst[i]=n+1;
	for(register int i=n;i>=1;--i){
		suf[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	for(register int i=1;i<=n;++i)
		pos[i]=makep(i,pre[i],suf[i],a[i]);
		
	kdt.root=kdt.build(1,n,0);

	int ls=0;
	while(m--){
		int x=read(),y=read(),l=Min(x,y,ls),r=Max(x,y,ls);
		write(ls=kdt.query(l,r)),putchar('\n');
	}
	return 0;
}

BZOJ4154 Generating Synergy

对于一个有根带点权树，支持两个操作：子树修改距根不超过 kk 的点的点权；单点查询点权。

n,m,ai≤105n,m,a_i\leq 10^5。

题解

二维线段树显然可以做这个题，现在考虑如何用 KDTree 解决。

如果我们求出树上每个点的深度和其对应子树的 dfn 区间，记为 depi,dfni,outidep_i,dfn_i,out_i。

则子树修改等价于修改满足 dfni∈[dfnx,outx],depi∈[depx,depx+k]dfn_i\in[ dfn_x,out_x ],dep_i\in[dep_x,dep_x+k] 的点 ii 的权值。将 dfn,depdfn,dep 看成横纵坐标，单次修改就相当于矩形内所有点赋值、单点查寻。因为不需要动态地加点删点，只需要给 KD-Tree 搞上一个区间赋值的下传标记即可实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
const int max_n=200005;const long long mod=1000000007;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
	int ct,nx[max_n*2],to[max_n*2],hd[max_n];
	graph(){ct=1;}
	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}

int n,c,Q;

int dep[max_n],dfn[max_n],out[max_n],cntdfn;
inline void dfs(int u,int dp){
	dfn[u]=++cntdfn,dep[u]=dp;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		dfs(v,dp+1);
	}
	out[u]=cntdfn;
}

struct point{
	int x,y,val;
	point(){x=y=val=0;}
	bool operator == (const point b) const{
		point a=*this;
		return (a.x==b.x && a.y==b.y);
	}
}p[max_n],q[max_n];
inline point makep(int a,int b,int v){
	point res;
	res.x=a,res.y=b,res.val=v;
	return res;
}
bool cmpt;
inline bool cmp(point a,point b){
	if(cmpt) return a.x<b.x;
	return a.y<b.y;
}

struct KDTree{
	int root,tot;
	struct dot{
		point x,l,r;
		int sz,tp,ls,rs,tg;
		dot(){sz=tp=ls=rs=tg=0;}
	}a[max_n];
	#define ls(x) (a[x].ls)
	#define rs(x) (a[x].rs)

	inline void pushup(int x){
		a[x].l=a[x].r=a[x].x;
		a[x].sz=a[ls(x)].sz+a[rs(x)].sz+1;
		if(ls(x)){
			a[x].l.x=min(a[x].l.x,a[ls(x)].l.x),a[x].r.x=max(a[x].r.x,a[ls(x)].r.x);
			a[x].l.y=min(a[x].l.y,a[ls(x)].l.y),a[x].r.y=max(a[x].r.y,a[ls(x)].r.y);
		}
		if(rs(x)){
			a[x].l.x=min(a[x].l.x,a[rs(x)].l.x),a[x].r.x=max(a[x].r.x,a[rs(x)].r.x);
			a[x].l.y=min(a[x].l.y,a[rs(x)].l.y),a[x].r.y=max(a[x].r.y,a[rs(x)].r.y);
		}
	}
	inline void pushdown(int x){
		if(!a[x].tg) return;
		//cerr<<"pushdown! : "<<x<<"\n";
		if(ls(x)) a[ls(x)].tg=a[ls(x)].x.val=a[x].tg;
		if(rs(x)) a[rs(x)].tg=a[rs(x)].x.val=a[x].tg;
		a[x].tg=0;
	}
	inline int build(int l,int r,int t){
		int x=++tot,mid=(l+r)>>1;
		cmpt=t;
		nth_element(p+l,p+mid,p+r+1,cmp);
		a[x].tp=t,a[x].x=p[mid],ls(x)=rs(x)=a[x].tg=0;
		t=rand()^1;
		if(l<mid) ls(x)=build(l,mid-1,t^1);
		if(r>mid) rs(x)=build(mid+1,r,t^1);
		pushup(x);
		return x;
	}
	inline void upd(int x,point i,point j,int val){
		if(a[x].l.x>j.x || a[x].r.x<i.x || a[x].l.y>j.y || a[x].r.y<i.y)
			return;
		if(a[x].l.x>=i.x && a[x].r.x<=j.x && a[x].l.y>=i.y && a[x].r.y<=j.y){
			a[x].x.val=val,
			a[x].tg=val;
			return;
		}
		if(a[x].x.x>=i.x && a[x].x.x<=j.x && a[x].x.y>=i.y && a[x].x.y<=j.y){
			a[x].x.val=val;
		}
		pushdown(x);
		if(ls(x)) upd(ls(x),i,j,val);
		if(rs(x)) upd(rs(x),i,j,val);
	}
	inline int ask(int x,point i){
		if(a[x].x==i)
			return a[x].x.val;
		cmpt=a[x].tp;
		pushdown(x);
		if(cmp(i,a[x].x)) return ask(ls(x),i);
		return ask(rs(x),i);
	}
}kdt;

signed main(){
//	freopen(".in","r",stdin),
//	freopen(".out","w",stdout);
	int T=read();
	while(T--){
		n=read(),c=read(),Q=read();
		e.clear();
		for(register int i=2;i<=n;++i){
			int fa=read();
			e.add(fa,i);
		}
		long long ans=0;
		cntdfn=kdt.root=kdt.tot=0;
		dfs(1,1);
		for(register int i=1;i<=n;++i){
			p[i]=q[i]=makep(dfn[i],dep[i],1);
		}

		kdt.root=kdt.build(1,n,1);
		for(register int i=1;i<=Q;++i){
			int a=read(),l=read(),c=read();
			if(c){
				kdt.upd(kdt.root,makep(dfn[a],dep[a],0),makep(out[a],dep[a]+l,0),c);
			}
			else{
				int tmp=kdt.ask(kdt.root,q[a]);
				ans+=(long long)i*tmp%mod;
				ans%=mod;
			}
		}
		write(ans),putchar('\n');
	}
	return 0;
}
  • 标题: 替罪羊树与 KDTree
  • 作者: Arahc
  • 创建于 : 2021-11-25 08:00:00
  • 更新于 : 2023-03-18 13:27:58
  • 链接: https://arahc.github.io/2021/11/25/【笔记】替罪羊树与-KDTree/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
替罪羊树与 KDTree
  1. 前言
  2. 替罪羊树
  3. KDTree
    1. 建树
    2. 重构
    3. 估价
  4. 例题