一些有点容易忘的基础算法

发表于 更新于 分类于

树链剖分

常用的树链剖分有重链剖分，实链剖分和长链剖分。

长链剖分主要用于部分和深度有关的树形 \(dp\) 的优化，一般采用指针数组实现。

我们说的树链剖分一般指重链剖分，即选择每个点子树最大的儿子。

不难证明从任何一个点到根都只会经过 \(log_n\) 条重链，这也是其复杂度的保证。

可以将每条重链用一个数据结构维护起来，就能做树上操作了。

动态树

动态树是基于实链剖分的数据结构，非常强大，但编码复杂度相对较高。

我使用的是基于 \(splay\) 的动态树。

动态树维护的是若干实链，每个实链用一颗平衡树维护。

动态树的核心操作是 access，意味将目标点 \(x\) 到根的路径全部打通，并且只包含这条路径。

其它操作简要介绍一下实现：

make_root :先 access，然后把 \(x\) splay 到根，然后翻转整颗 \(splay\) ，因为 \(splay\) 外的形态没有改变，所以只要 \(splay\) 内部的形态正确，那么整棵树的形态就正确，如果对于一个 \(splay\) 所有的节点交换了左右儿子，那么就是倒序了这颗 \(splay\) ，\(x\) 又是深度最大的点，所以这样是正确的。

link :很简单，直接将目标点 \(x\) splay 到当前根，当然，注意到原树之间的关系是 \(splay\) 根节点的关系，\(splay\) 根节点的父亲其实是 \(splay\) 中深度最小的点的父亲，然后改父亲改成 \(y\) 就行。

cut :假设有一个虚根 \(0\)，把 \(x\) make_root ，把 \(y\) access 然后 splay \(y\),直接双向断开。

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
void push_up(int rt){}
//该更新的要更新
void push_down(int rt){}
//旋转标记和其它标记的 push_down
bool isroot(int rt){return T[T[rt].fa].son[0]!=rt&&T[T[rt].fa].son[1]!=rt;}
void rotate(int x)
{
	int y=T[x].fa,z=T[y].fa,o=T[y].son[1]==x,b=T[x].son[o^1];
	if(!isroot(y))T[z].son[T[z].son[1]==y]=x;
	T[y].fa=x;T[x].son[o^1]=y;T[x].fa=z,T[y].son[o]=b,T[b].fa=y;
	push_up(y),push_up(x);
    //已经很熟的 rotate 操作
}
void splay(int x)
{
	int u=x;st[++top]=u;
	while(!isroot(u))u=T[u].fa,st[++top]=u;
	while(top)push_down(st[top--]);
    //记得先 push_down
	
	for(int y=T[x].fa;!isroot(x);y=T[x].fa)
	{
		if(!isroot(y))rotate((T[T[y].fa].son[1]==y)==(T[y].son[1]==x)?y:x);
        //双旋，其实一般单旋也不会卡。
		rotate(x);
	}
    //亲切的 splay 操作
}
void access(int x,int y=0)
{
    //记得断开和儿子的连接
    //splay 之间是原树的关系连接，但 splay 内部维护的只是一条链，中序遍历 splay 才能得到原树
	for(;x;y=x,x=T[x].fa)
	{
		splay(x);T[x].son[1]=y;
		push_up(x);
	}
}

虚树：

一般用来处理询问很多但规模不大的树上问题。

点分治

用来处理树上路径的计数问题，特别是路径长度相关

后缀排序

对一个字符串的所有后缀排序，约定 \(sa[i]\) 表示排名为 \(i\) 的后缀的起始位置，约定 \(rk[i]\) 表示起始位置为 \(i\) 的后缀的排名。\(height[i]\) 为排名为 \(i,i-1\) 的后缀的 \(lcp\) 。

先按第一个字母基数排序一遍，然后倍增法。

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
for(i=1;i<=n;i++)sum[rk[i]=ch[i]]++;
for(i=1;i<=128;i++)sum[i]+=sum[i-1];
//统计 sum,sum[i] 表示关键字比 i 小的总个数，然后遍历的时候，用每个后缀当前排名访问 sum，
//得到 sum[rk[i]] 为以 i 为起始位置的后缀的排名。
//访问后 sum 需要自减。
//但并不记录这个排名，因为它不准确，相同的会认为是不同，记录排名为 sum[rk[i]] 的后缀的起始位置。
for(i=n;i>=1;i--)sa[sum[rk[i]]--]=i;
for(i=1;i<=n;i++)tp[i]=rk[i];
for(i=1;i<=n;i++)rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]])?m:++m;
//这里重新计算每个后缀的排名，我们可以简单由 sa 数组得到。
for(k=1;;k<<=1)
{
    m=s=0;
    for(i=n-k+1;i<=n;i++)tp[++s]=i;
    //这些第二关键字为 0 ，所以仍在最前面
    //tp[i] 在这里表示第二关键字排名为 i 的后缀的起始位置
    //这里在按第二关键字安排顺序，第一遍在外面排序的时候不关心第二关键字
    //在倍增里排序关心第二关键字，我们只需要按第二关键字的顺序访问 sum，就能得到正确顺序。
    for(i=1;i<=n;sum[i++]=0)if(sa[i]>k)tp[++s]=sa[i]-k;
    //同样是处理第二关键字，按照上一轮排名顺序遍历即可。
    //位置减去 k,得到第二关键字的起始位置。
    for(i=1;i<=n;i++)sum[rk[i]]++;
    for(i=1;i<=n;i++)sum[i]+=sum[i-1];
    for(i=n;i>=1;i--)sa[sum[rk[tp[i]]]--]=tp[i];
    //同样的道理，只不过是按第二关键字大小顺序遍历
    for(i=1;i<=n;i++)tp[i]=rk[i];
    //这里的 tp 用来拷贝 rk,因为 rk 在计算时会改变
    for(i=1;i<=n;i++)rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?m:++m;
    //计算每个后缀当前排名
    if(m==n)break;
    //后缀排序结束后退出。
}
//计算 height 数组
//height 数组满足 height[sa[i]] >= height[sa[i]-1] - 1
//如果 sa[i] = 1，那么 height 没定义，不管。
//原因很简单，以  排名在以 sa[i]-1 为起始点的后缀 x 前一个的后缀 y。
//由定义 lcp(x,y) = height[sa[i]-1]
//将 x 删掉最前一个字符得到以 sa[i] 为起始点的后缀 a， y 删掉最前一个字符得到 b
//那么 lcp(a,b) = lcp(x,y)
//显然 b 排在 a 前面
//显然排名在 a 前一位的那个后缀与 a 的 lcp 不可能少于 height[sa[i]-1]
for(i=1;i<=n;i++)
{
    height[rk[i]]=max(0,height[rk[i-1]]-1);
    if(rk[i]==1)continue;
    while(ch[i+height[rk[i]]+1]==ch[sa[rk[i]-1]+height[rk[i]]+1])height[rk[i]]++;
}

莫队

莫队是暴力数据结构，将询问离线后，以较低的复杂度移动左右端点，然后处理询问。

设移动端点的复杂度为 \(O(x)\) ，那么莫队复杂度为 \(O(n \sqrt n\times x)\)，无法将 \(x\) 放在 \(\sqrt n\) 下面。

常见的卡常技巧有奇偶性排序等。

如果只能支持插入和删除中的一种操作，那么可以使用回滚莫队，拿一个栈记录操作，基于操作的撤销实现插入或删除。

树上莫队和普通莫队区别不大。

(差一个二次离线要补)

拓展KMP

咕咕咕

树哈希

一般来讲，可以这么哈希，再加上树大小的判断，就不会出问题。 \[ f_{now}=1+\sum f_{son(now,i)} \times prime(size_{son(now,i)}) \]

但这个哈希是有错的，可以对最小括号序列哈希。

具体的，一颗无标号有根树按照遍历顺序可以得到一个括号序列，即将子树的括号序列拼起来再套一个括号。

然后考虑对这个括号序列哈希，因为遍历顺序无关，所以要最小括号序列。

实际上可以直接对子树哈希值排序之后，按这个顺序往后写，外面添一层括号，对括号序列（二进制串）哈希。