【全】笛卡尔树学习笔记

· · 算法·理论

背景

发现自己不会笛卡尔树，于是前去 oi-wiki 学习并完成了部分例题。

这篇文章将会详细讲解笛卡尔树，基本是作者自己经过学习提炼出的核心内容。

笛卡尔树（正文）

定义

不讨论空树，笛卡儿树是一棵二叉树，其中每个节点有一个二元组信息 (k, w) 且 k 满足二叉搜索树的性质，w 满足达大根堆或小根堆的性质。我习惯称之为大根笛树和小根笛树（非官方）。

重要性质

我们这里讨论对任意正整数序列（元素值互不相同）构建小根笛树。

当一棵笛卡尔树的所有 (k, w) 确定时，树的结构是唯一的，这个性质非常关键。证明比较容易，使用归纳法即可。

一棵子树对应原序列的一个区间。[l, r] 之间的最小值是树上 \operatorname{LCA}(u, v) 的 w 权值。

构建

我们这里仍然讨论对任意正整数序列（元素值互不相同）构建小根笛树。形式化地，(k, w) 表示 (i, a_i) 且编号为 i，即我们希望下标满足二叉搜索树性质而权值满足小根堆的性质。

借 oi-wiki 图一用。

那么我们考虑从左往右依次将 (i, a_i) 插入笛卡尔树，注意本质上这个限制了第一关键字的递增顺序。仍以上图为例，我们给出这个序列的建树过程图（oi-wiki）。

红色部分表示笛卡尔树的右链。通过这个过程，我们能总结出插入（假设树非空）的策略。我们通过某种手段维护出这个右链，由于 w 权值是递增的，我们从下往上找到第一个满足 w 小于 w_i 的点（若没有则为 0）。若存在，则将 i 设为这个节点的右儿子，并将下面的部分接在 i 的左儿子部分（若存在）。正确性是显然的，k 和 w 的大小性质都能正确地维护。

那么如何维护右链呢？显然我们使用一个栈来维护即可。（某些地方称为单调栈，但其实就是普通的栈）由于每个元素最多进出一次栈，整个建树的时间复杂度是 \Theta(n) 的。这里以 n 在 10 ^ 7 范围内，正整数 a_i 在 int 范围内给出代码（改编自 oi-wiki）。

// stk 维护笛卡尔树中节点对应到序列中的下标
for (int i = 1; i <= n; i++) {
    int tp = top;  // top 表示操作前的栈顶，tp 表示当前栈顶
    while (tp && w[stk[tp]] > w[i]) k--;  // 维护右链上的节点
    if (tp) rs[stk[tp]] = i;  // i 父亲存在
    if (tp < top) ls[i] = stk[tp + 1];  // 当前元素.左儿子 := 上一个被弹出的元素
    stk[top = ++tp] = i; // 将 i 插入右链
}

应用

这里以例题形式讲解笛卡尔树的应用。

Hdu1506 最大子矩形

题目翻译：若干组数据，每次给出 n 表示矩形数量，h_i 表示高度，宽度都为 1，求最大子矩形大小（保证时空线性复杂度能通过）。1 \le n \le 10 ^ 5, 0 \le h_i \le 10 ^ 9。

题解（也是我的）。

P1377 树的序

如果我们能建出树那么跑一遍先序遍历即可。但是如果模拟题目的建树方式显然时间复杂度 O(n ^ 2)。

观察性质可以发现这棵树以权值对 (k_i, i) 为小根笛树。于是我们使用单调栈构建即可，记得要按照 k 从小到大加入，否则构建是错误的！

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, k[N], root, ls[N], rs[N], top, stk[N];

void dfs(int u) {
    cout << k[u] << ' ';
    if (ls[u]) dfs(ls[u]);
    if (rs[u]) dfs(rs[u]);
    return void();
}

vector <int> vec;
inline bool cmp(const int x, const int y) { return k[x] < k[y]; }

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> k[i], vec.emplace_back(i);
    sort(vec.begin(), vec.end(), cmp);
    for (const int &x : vec) {
        int tp = top;
        while (tp && stk[tp] > x) --tp;
        if (tp) rs[stk[tp]] = x;
        else root = x;
        if (top && tp < top) ls[x] = stk[tp + 1];
        stk[++tp] = x, top = tp;
    }
    dfs(root);
    return 0;
}

后记

好的题单：笛卡尔树题单。

感谢阅读！