「学习笔记」省选数据结构复习

突然发现自己很多数据结构长时间不做题导致连几乎是模板题都不会，于是写一篇复习笔记，以后复习的时候可以直接看看笔记。感觉自己忘不了的就没写说明，也有可能是我还不会。

待学：

• KD-Tree
• LCT

还需要多写代码加强理解：

• 平衡树
• 树套树

非旋 treap

码量小，好写，常数小。

基础：采用宏定义左右儿子来减少码量。$c$ 为随机的权值。

mt19937 rnd(time(NULL)^(ull)(new char));
int trnt,rt;
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int siz[N],c[N],v[N],ch[N][2];
inline void pushup(int x){siz[x]=siz[ls(x)]+siz[rs(x)]+1;}
inline int newnode(int va){int x=++trnt;siz[x]=1;ch[x][0]=ch[x][1]=0;c[x]=rnd();v[x]=va;return x;}

split(u,k,&x,&y)，将以 $u$ 为根的节点分裂，$\leq k$ 的节点给 $x$，$>k$ 的给 $y$，根据 $v[u]$ 来判断当前节点是给 $x$ 还是 $y$，然后递归分裂下去。

由于分裂之后当前节点的子树信息发生了变化（有一部分分裂出去了），所以要 pushup 一下。

void split(int u,int k,int &x,int &y){
	if(!u){x=y=0;return ;}
	if(v[u]<=k)x=u,split(rs(u),k,rs(x),y);
	else y=u,split(ls(u),k,x,ls(y));
	pushup(u);
}

merge(x,y)，将 $x$ 和 $y$ 为根节点的平衡树合并，用随机的权值 $c$ 来判断谁当根，然后递归下去合并。同理，树的结构会发生改变，要 pushup 一下。

采用三目运算符减少码量。

int merge(int x,int y){
	if(!x||!y)return x|y;
	int k=c[x]<c[y],u=k?x:y;
	ch[u][k]=merge(k?rs(x):x,k?y:ls(y));
	pushup(u);return u;
}

kth(x,k)，在以 $x$ 为根的平衡树里找到排名为 $k$ 的节点，用递归可以减少码量。

int kth(int x,int k){
	if(k<=siz[ls(x)])return kth(ls(x),k);
	if(k==siz[ls(x)]+1)return x;
	return kth(rs(x),k-siz[ls(x)]-1);
}

基于这三个基本操作，能够完成大部分的平衡树基础操作，注意 split 完要 merge，而且不要忘了把最后 merge 的根赋给 rt。

namespace fhq_treap{
	mt19937 rnd(time(NULL)^(ull)(new char));
	int trnt,rt;
	#define ls(x) ch[x][0]
	#define rs(x) ch[x][1]
	int siz[N],c[N],v[N],ch[N][2];
	inline void pushup(int x){siz[x]=siz[ls(x)]+siz[rs(x)]+1;}
	inline int newnode(int va){int x=++trnt;siz[x]=1;ch[x][0]=ch[x][1]=0;c[x]=rnd();v[x]=va;return x;}
	void split(int u,int k,int &x,int &y){
		if(!u){x=y=0;return ;}
		if(v[u]<=k)x=u,split(rs(u),k,rs(x),y);
		else y=u,split(ls(u),k,x,ls(y));
		pushup(u);
	}
	int merge(int x,int y){
		if(!x||!y)return x|y;
		int k=c[x]<c[y],u=k?x:y;
		ch[u][k]=merge(k?rs(x):x,k?y:ls(y));
		pushup(u);return u;
	}
	int kth(int x,int k){
		if(k<=siz[ls(x)])return kth(ls(x),k);
		if(k==siz[ls(x)]+1)return x;
		return kth(rs(x),k-siz[ls(x)]-1);
	}
	int _a,_b,_c;
	#define a _a
	#define b _b
	#define c _c
	void ins(int x){split(rt,x,a,b);rt=merge(merge(a,newnode(x)),b);}
	void del(int x){split(rt,x,a,c);split(a,x-1,a,b);rt=merge(a,merge(merge(ls(b),rs(b)),c));}
	int findrk(int x){split(rt,x-1,a,b);int s=siz[a]+1;rt=merge(a,b);return s;}
	int findval(int x){return v[kth(rt,x)];}
	int lst(int x){split(rt,x-1,a,b);int s=v[kth(a,siz[a])];rt=merge(a,b);return s;}
	int nxt(int x){split(rt,x,a,b);int s=v[kth(b,1)];rt=merge(a,b);return s;}
	#undef a
	#undef b
	#undef c
}

fhq_treap 维护区间也是简单的。例如要把 $[l,r]$ 区间操作，即可先把 $[l,r]$ 内的节点分裂出一个平衡树，在根上打个标记，然后再合并回去即可。每次递归往下走的时候记着要下放标记。

Splay

基于旋转（rotate）及其实现的伸展（splay）操作的平衡树。

太难写了于是鸽掉了！

线段树合并/分裂

假如要合并以 $x$ 为根和以 $y$ 为根的线段树：

• $x$ 或 $y$ 为空，返回 $x+y$；
• 当为叶子时，直接更新节点信息并返回；
• 递归将 $ls(x)$ 和 $ls(x)$ 合并成新节点（或者仍为 $x$，因题而异）的 $ls$，右儿子同理。

复杂度分析：每次合并的复杂度为两棵线段树重合的点数，同时也是一次合并后删去的点数，由于初始 $n$ 个单点产生的线段树节点个数为 $\mathcal{O}(n\log n)$，所以总复杂度为 $\mathcal{O}(n\log n)$。

分裂：split(x,&y,k) 将 $x$ 为根的线段树维护的前 $k$ 个划分给 $k$，其余的给 $y$．像线段树上二分走然后每次走的给 $y$ 新建节点即可，注意如果 $x$ 的整棵子树都要给 $y$，那么直接将 $x$ 指向这棵子树的边断掉，让 $y$ 连上即可。

这样分裂的时候每一层只会遍历到一个节点，所以分类操作总新建点数是 $\mathcal{O}(n\log n)$ 级别了，这同时也保证了合并操作与分裂操作同时存在时合并操作复杂度的正确。

笛卡尔树

每个节点都是一个二元组 $(k,w)$，其中 $k$ 满足二叉搜索树限制，$w$ 满足小根堆限制。常见应用是将序列 $a$ 刻画为 $(i,a_i)$，同时也等价于最值分治的结构。（类似于线段树是中点分治的结构）

构建方法：

• 维护一条 $w$ 递增的右链，按照 $k$ 为关键字排序之后一个个插入。
• 每次插入节点 $i=(k’,w’)$ 的时候在这条右链上找到从底向上第一个 $w<w’$ 的节点 $x$，那么将 $i$ 挂到 $x$ 的父亲上，$x$ 挂到 $i$ 上即可。

常见的应用是笛卡尔树上 dp，也可以理解为最值分治。

虚树

就是只包含原树中关键点以及它们之间两两 LCA，将原树中不重要的链压缩成一条边。

构建方法：

• 由于多加点并不会影响答案，先将根节点加进去。用栈维护一条从根节点出发的链，栈顶是深度最深的节点。
• 按照 dfs 序从小到大依次插入，设当前插入节点 $x$ 于栈顶 $st[top]$ 的 LCA 为 $t$：
• 若 $dep_t< dep_{st[top-1]}$：说明 $t$ 在 $st[top-1]$ 之前，$add(st[top-1],st[top])$ 并弹出栈顶，继续判断；
• 若 $dep_{st[top-1]}\leq dep_t<dep_{st[top]}$：说明 $t$ 介于 $st[top-1]$ 和 $st[top]$ 之间。将 $add(t,st[top])$ 并弹出 $st[top]$，若 $t$ 和 $st[top-1]$ 不同则还需要将 $t$ 入栈，然后将 $x$ 入栈，此轮插入结束；
• 若 $t=st[top]$，说明 $st[top]$ 就是 $x$ 的祖先，直接将 $x$ 入栈即可，此轮插入结束。
• 最后栈中还有剩余的元素，再把他们连起来就行。

基于此，在 $\mathcal{O}(k\log k)$ 的时间复杂度内建出了虚树（$k$ 为关键点数量），同时也说明了虚树的点数是 $\mathcal{O}(k)$ 的（每轮插入最多会插入 $1$ 个非关键点）。

有的时候不一定给的点就是要建虚树的关键点，也有可能包含其他重要的点。总之就是保留哪些不会影响答案就保留哪些。

例题 Codeforces 613 D

长链剖分

重链剖分是基于子树大小进行链剖，而长链剖分则是根据子树内最深深度作为优先级来划分轻重儿子。

重链剖分和长链剖分共同的性质：

• 重（长）链个数等于叶子节点个数。因为链的终点只能是叶子（非叶节点一定有重儿子）。

长链剖分性质：

• 一个点祖先中轻儿子个数是 $\mathcal{O}(\sqrt n)$ 级别的，也就是其到根节点路径上长链个数是 $\mathcal{O}(\sqrt n)$ 的。考虑每次进入一个新的长链时，新的长链至少是当前长链节点个数 $+1$，那么最劣情况下经过的长链长度为 $1,2,3,\cdots$ 最多 $\mathcal{O}(\sqrt n)$ 个长链。

长链剖分经典应用是树上 k 级祖先和维护深度有关信息。

树上 k 级祖先

长链剖分，并且预处理出每个节点 $2^i$ 级祖先。对于每个长度为 $len$ 的长链，还有预处理出链顶向（长链方向）下 $len$ 个儿子和向上 $len$ 个祖先。

每次询问 $x$ 的 $k$ 级祖先：

• 对于 $k$ 的最高位 $2^r$，首先有 $2^r\leq k< 2^{r+1}$，将 $x$ 跳到其 $2^r$ 级祖先 $x’$ 处；
• 即求 $x’$ 的 $k’\gets k-2^r$ 级祖先，则有 $0\leq k’<2^r$；
• 由于 $x’$ 所在长链长度 $\geq 2^r$，所以 $x’$ 的 $k$ 级祖先一定是链顶 $t$ 已经预处理过的儿子或者父亲，直接算出来即可。

复杂度 $\mathcal{O}(n\log n)-\mathcal{O}(1)$，只是理论复杂度，由于常数原因可能打不过重剖或者倍增。

维护深度有关信息

另一个常见的应用是维护深度有关的信息，比方说长链剖分优化 dp，这个需要用指针来分配内存达到 $\mathcal{O}(n)$ 空间消耗，首先先给每个长链的链顶都分配链长度的内存，非链顶和其父亲共用一处内存，要偏移一位，即 $f_v=f_x+1$．合并的时候由于重儿子和自己共用一处内存可以直接继承，轻儿子暴力合并上来，时空复杂度均为 $\mathcal{O}(n)$．注意在合并后重儿子的信息被破坏了，所以这是一个离线的做法。

模板题 CF1009F

核心代码：

int buf[N],*f[N],*p=buf;
void dfs1(int x,int fa){
	for(auto v:eg[x])if(v!=fa){
		dfs1(v,x);
		if(mxd[v]>mxd[son[x]])son[x]=v;
	}
	mxd[x]=mxd[son[x]]+1;
}
void dfs2(int x,int fa){
	f[x][0]=1;
	if(son[x]){
		f[son[x]]=f[x]+1;
		dfs2(son[x],x);
	}
	for(auto v:eg[x])if(v!=son[x]&&v!=fa){
		f[v]=p;p+=mxd[v];
		dfs2(v,x);
		for(int i=0;i<mxd[v];i++)f[x][i+1]+=f[v][i];
	}
}

李超树

插入直线/线段，支持查询单点极值。

就是线段树对于每个区间维护在 $m=\frac{l+r}{2}$ 处取值最大的直线的信息。

现在我们需要插入一条线段 $f$，在这条线段完整覆盖的区间中，某些区间的最优线段可能发生改变。

考虑某个被新线段 $f$ 完整覆盖的区间，若该区间无最优线段，则该线段可以直接成为最优线段。

否则，设该区间的中点为 $m$，我们拿新线段 $f$ 在中点处的值与原最优线段 $g$ 在中点处的值作比较。

如果新线段 $f$ 更优，则将 $f$ 和 $g$ 交换。那么现在考虑在中点处 $f$ 不如 $g$ 优的情况：

1. 若在左端点处 $f$ 更优，那么 $f$ 和 $g$ 必然在左半区间中产生了交点，递归到左儿子中进行插入；
2. 若在右端点处 $f$ 更优，那么 $f$ 和 $g$ 必然在右半区间中产生了交点，递归到右儿子中进行插入。

由于仅有一个交点，所以两边最多会递归一个。复杂度 $\mathcal{O}(\log n)$．

这种写法比 oi-wiki 上的写法好写到不知道哪里去了！

查询 $x=k$ 答案时，从根走到 $[x,x]$ 节点记录的所有最优直线在 $x=k$ 时取值的答案极值即为所求。这里是运用了标记永久化的思想。

Extension：

• 如果是插入线段，需要定位到线段横坐标区间在李超树上的拆分出的区间，然后一个个递归修改下去，复杂度是 $\mathcal{O}(\log^2n)$ 的。
• 李超树不能删除直线，所以想李超树这样不支持删除的数据结构遇到删除的问题要线段树分治。
• 李超树合并，势能分析一下是 $\mathcal{O}(n\log n)$ 的。

李超树的经典应用是斜率优化，关于此我之前写过的总结：

化柿子的时候化成一次函数的形式更直观一些（对我来说）。

如果是单调栈上二分 / 单调队列，这一类的，通常都是斜率或者某些东西具有单调性，这个东西不需要也尽量不要对每一种情况都整理下来应该怎么优化，是死板的。斜率优化是把一类 dp 问题变成数据结构问题，让数据结构维护这个凸包（或者说维护凸包上两点连线的斜率），应该具体情况具体分析。

如果加的决策点没有单调性，通常是 平衡树 / CDQ 分治 来解决，平衡树的话就是直接维护这个凸包，CDQ 分治则是通过分治来转成静态问题，然后用单调栈等数据结构解决。

有一种更普遍的做法，跳出维护凸包给我们思维上的限制，用李超树来维护一次函数（直线），也是一个 $\log$ 的，而且码力要求和常数上肯定都优于平衡树，但常数还有可能比较大（相比 CDQ 分治来说？），但不需要动脑子（也就是前文说的具体情况具体分析，分析哪些变量是单调的，这个凸包的形状是怎样的，依次加进去的决策点坐标的单调性，截凸包的直线斜率的单调性…），论性价比李超树也是一个很好的选择。

树套树

到底有没有用啊/fn

线段树套线段树（二维线段树？），注意到外层的线段树信息无法合并，因为信息合并的话相当于内层线段树进行线段树合并。所以要不然标记永久化，要不然就只能做到单点修改。

比方说矩形加矩形求和：假设对 $[L_1,R_1],[L_2,R_2]$ 的矩形加 $v$，首先在外层线段树上定位 $[L_1,R_1]$，如果当前节点区间 $[l,r]$ 被 $[L_1,R_1]$ 完全包含，直接打个标记；否则将内层线段树的 $[L_2,R_2]$ 区间加上 $v$ 乘上 $[l,r]$ 和 $[L_1,R_1]$ 交集大小的修改量。

BIT 套线段树，严格不强于上一个，但是码量相对较小，不过其实线段树套线段树充其量也就是写两编线段树？

线段树分治

对此的记忆刻画不是很深刻，虽然不是数据结构但通常在数据结构题中出现。

离线算法，假如要维护的数据结构仅支持插入，可能不支持删除，但要支持撤销，即删除最近一次修改。

在时间上建线段树，对于一个加入操作，假设它在时间轴上的持续区间为 $[l,r]$，那么在线段树上 $[l,r]$ 拆分出的每个区间都加入这个操作。最后在线段树上 dfs，走进一个点的时候加入里面的操作，走出一个点时候撤销里面的操作。那么 时刻 $t$ 的线段树就是从根节点走到 $[t,t]$ 节点时的线段树。

当然，也可以不在时间轴上分治，在其他维度上分治，一个例题是 [CTSC2016]时空旅行。

题目口胡

因为没时间一个个写了。

洛谷 P2056 [ZJOI2007]捉迷藏 / SPOJ QTREE4

树，维护点集，插入/删除/询问点集直径。

又有插入又有删除的，上一发线段树分治这样只有插入和撤销。撤销通常情况下是简单的，现在问题变成每次将一个点染成黑色，询问黑点中里面两两距离最大值。

那就考虑每次加入的时候询问这个点和点集里面距离的最大值，建一发点分树，对于每个分治重心 $x$ 维护一个 $mx_1$ 和 $mx_2$，$mx_1$ 代表 $x$ 在点分治的连通块里面距离 $x$ 最远的黑点，$mx_2$ 是与 $mx_1$ 不在 $x$ 同一子树内的最远的黑点。

这样每次询问的时候，对于 $x$ 在点分树上的一个父亲 $f$，如果 $x$ 和 $mx_1$ 不在同一子树内就用 $mx_1$ 更新答案，否则就用 $mx_2$ 更新答案。那么插入和撤销也是简单的。

这样复杂度就是 $\mathcal{O}(m\log n\log m)$ 的了。

有更简单的做法/fn

重新看一下问题，插入删除询问点集直径。经典结论是两个点集并起来的直径端点一定在两个点集分别的直径端点这四个点中。那么在编号维上用线段树维护这个东西，每次是一个单点修改，合并的时候用 ST 表 $\mathcal{O}(1)$ 查 LCA 就能做到优秀的 $\mathcal{O}(n\log n+m\log n)$！

洛谷 P5327 [ZJOI2019]语言

编了一个弱智做法是树剖然后变成在 $dfn\times dfn$ 平面上 $\log^2$ 个矩形覆盖，查询非零位置个数，扫描线一下是 $\mathcal{O}(n\log^3n)$ 目测常数还很大。但是在洛谷上卡过去了。

正解是考虑，如果对每个点单独计算它能到达的点的话，那就是经过这个点所有路径并的大小，也就是所有路径端点构成的虚树大小，这个长度等于所有点按照 dfn 排序相邻两两距离之和 $\div 2$（包括头尾）。由于是静态路径加入两个点，树上差分一下，这样一个节点的虚树点集实际上是其和所有儿子虚树点集的并，用线段树合并来维护即可。

洛谷 P3206 [HNOI2010]城市建设

一眼看出了线段树分治 + LCT 的 $\mathcal{O}(q\log n\log q)$ 做法，但是不会写 LCT 哈哈。

没有用到 LCT 的做法非常智慧，怎么想出来的？？：

这里不是线段树分治，而是单纯的在时间维上分治。考虑分治过程中缩小图的规模：

• $[L,R]$ 内会进行修改的边边权都改成 $-\infty$，跑 mst，此时在 mst 上的非 $-\infty$ 边是必须要选的，可以直接把点缩起来；
• $[L,R]$ 内会进行修改的边边权都改成 $\infty$，跑 mst，此时不在 mst 上的边一定是必须不选的，直接删掉。

在第一个操作之后，最多会留 $R-L$ 个点（最劣情况下是所有 $-\infty$ 边都在 mst 中），而第二个操作后会保证边数和点数同阶。

这样复杂度就是 $T(n)=2(\frac{T}{2})+\mathcal{O}(q\log q)=\mathcal{O}(q\log^2q)$．

洛谷 P6623 [省选联考 2020 A 卷] 树

从低位到高位建 Trie，这样就能支持全局加 1 就是 $\log$ 个节点和其兄弟 swap，然后搞个 Trie 合并，要维护个子树权值和以及子树 size，复杂度是 $\mathcal{O}(n\log n)$，有时间写写看看会不会被卡常。

参考资料

Alex_Wei 线段树的高级用法

oi-wiki

xtx1092515503 的博客