笛卡尔树学习笔记

TernaryTree · 2023-05-21 12:29:05 · 算法·理论

前言

笛卡尔树是一种比较小众但是十分好用的数据结构，一般用于维护连续区间值的大小关系等。

笛卡尔树可以做到以下算法/数据结构的功能（即合多为一）：

ST 表
单调栈
悬线法

笛卡尔树基础应用不多，但是可以将动态规划等思想套用在序列的笛卡尔树上，本文会根据例题详解。

定义

在学习笛卡尔树如何构造之前，我们先要学习笛卡尔树是怎样一种数据结构。

笛卡尔树是基于一个静态序列的（不妨设其为 a）。根据这个序列 a，我们可以相应地构造出其笛卡尔树（不妨设结点 u 的权值为 b_u）。笛卡尔树需要满足：

笛卡尔树是二叉树。
笛卡尔树的权值中序遍历序列为 a。 也就是说，其编号中序遍历序列为 1\sim n。
笛卡尔树的权值满足小根堆/大根堆性质。即对于笛卡尔树上任意非根结点 u，设 fa 为其父亲，则必有 b_u\ge b_{fa}（小根堆），b_u\le b_{fa}（大根堆）。

借用一下 OI-wiki 上的图：

方便起见，笛卡尔树的结点编号与 a 序列下标共用。以下不再过多赘述。

性质

此处以小根笛卡尔树为例，解释笛卡尔树的性质。笛卡尔树有以下性质：

对于树上一条深度单调递增的路径，其权值单调不减。

证明：设路径为 \{p_1,p_2,p_3\dots ,p_m\}，则 p_i 为 p_{i+1} 父亲，根据定义 3 得到 b_{p_i}\le b_{p_{i+1}}。
对于任意两点 u,v（u\le v），以 \operatorname{lca}(u,v) 为根的子树恰好涵盖 a 序列中 [u,v] 区间的所有位置。换言之，即笛卡尔树中任意一个完整的子树的结点集合在 a 中连续。

由定义 2 易得。
对于任意两点 u,v（u\le v），其在笛卡尔树上的最近公共祖先的权值 b_{\operatorname{lca}(u,v)} 恰好等于 a 序列 [u,v] 区间的最小值。

证明：因为笛卡尔树满足小根堆性质，所以其每个子树也满足小根堆性质。对于以 \operatorname{lca} 为根的子树，必有其权值最小值为 b_{\operatorname{lca}(u,v)}。又由性质 2 可以得到其区间为 [u,v]，证毕。

构造

笛卡尔树可以在线性时空内构造。

考虑维护笛卡尔树上最右端的链。由定义 2,3 得到，这条链的编号和权值都不减。于是这条链可以看做一个维护位置的单调栈。

从前往后遍历 a 序列，设当前位置为 i，前 i-1 个位置的笛卡尔树已经构建好了。设当前的栈为 s，其栈顶（也就是右链最右端的元素位置）为 s_{top}。

如果 a_i\ge a_{s_{top}}，直接将 i 入栈，也可以理解为在笛卡尔树最右端的最下方挂上当前元素，不破坏笛卡尔树，如图：

括号里第一个元素表示位置，第二个元素表示权值。则此时栈内为 \{2,4,5\}，其对应权值为 \{1,3,4\}，由于新加入的 (6,6) 权值大于栈顶 4，所以直接将当前结点挂在 (5,4) 的右儿子即可。
否则，重复将 s_{top} 弹出（代码实现中表示为 top--），直到栈空或者满足 a_i\ge a_{s_{top}}。随后将位置 i 入栈，把最后一个弹出的元素 j 设为 i 的左儿子。

可以理解为，找到当前右链上的一条边，满足 b_i 介于边两端的权值之间，断掉这条边，然后将当前点插进去。这样也是满足笛卡尔树性质的。

每个点最多出入栈一次，所以总时间复杂度是 \Theta(n) 的。仅需要存每个点的左儿子右儿子和一个单调栈，所以空间复杂度也是 \Theta(n) 的。

代码实现如下：

for (int i = 1; i <= n; i++) {
    int top = cnt;
    while (top && p[s[top]] > p[i]) --top;
    if (top) rc[s[top]] = i;
    if (top < cnt) lc[i] = s[top + 1];
    s[cnt = ++top] = i;
}

算法替代

笛卡尔树实现 RMQ

由性质 3，笛卡尔树是可以做序列 RMQ 的。

笛卡尔树 RMQ 较 ST 表的优势：空间复杂度由 \Theta(n\log n) 降至 \Theta(n)。模板题：P3793 由乃救爷爷。

当然如果 RMQ 可离线，LCA 可以使用 tarjan 算法做到 \Theta(q) 的时间复杂度。

笛卡尔树实现单调栈

根据定义及性质树上递推即可。

例题

CF1748E Yet Another Array Counting Problem

比较简单的笛卡尔树上 dp。

根据大根堆性质建出笛卡尔树，那么 [l,r] 的“最左端最大值位置”就是 l 和 r 在笛卡尔树上的 \textrm{lca}。

若两个序列的所有“最左端最大值”都相等，那么意味着这两个序列所建出的笛卡尔树形态相同。转换为权值 \le m 的笛卡尔树计数问题。

不妨设 f_{u,j} 表示笛卡尔树上点 u 权值为 j，其子树的答案。则有

f_{u,j}=\sum_{k=1}^{j-1}f_{lc_u,k}\times \sum_{k=1}^{j}f_{rc_u,k}

时间复杂度 \Theta(\sum n\times m)。

void dfs(int u) {
    for (int i = 1; i <= m; i++) f[u][i] = 1;
    if (lc[u]) dfs(lc[u]);
    if (rc[u]) dfs(rc[u]);
    if (lc[u]) for (int i = 1; i <= m; i++) f[u][i] = f[u][i] * f[lc[u]][i - 1] % mod;
    if (rc[u]) for (int i = 1; i <= m; i++) f[u][i] = f[u][i] * f[rc[u]][i] % mod;
    for (int i = 2; i <= m; i++) f[u][i] = (f[u][i] + f[u][i - 1]) % mod;
}

P6453 [COCI2008-2009#4] PERIODNI

不妨先把笛卡尔树建出来，可以将图形切成若干个矩形。

一个经典结论是在 n\times m 的棋盘中放下 k 个可以横竖走的“车”，使他们两两互相不能攻击的方案数是 \dbinom{n}{k}\dbinom{m}{k}k!。

在此题中，结点 u 所代表的一个矩形长为 siz_u，宽为 a_u-a_{fa_u}。设 f_{u,i} 为 u 及其子树内放下 i 个点的方案数。则有

f_{u,i}=\sum_{j+k\le i}f_{lc_u,j}\cdot f_{rc_u,k}\cdot \dbinom{siz_u}{i-j-k}\dbinom{a_u-a_{fa_u}}{i-j-k}(i-j-k)!

把 j+k 看做整体，预处理前面的，然后 dp，就做完了。