跳至主要內容

笛卡尔树（2026.3.25）

Minecraftbucuo2026/3/25大约 8 分钟

笛卡尔树（2026.3.25）

笛卡尔树（Cartesian Tree） 是一种特殊的二叉树数据结构，它巧妙地结合了 二叉搜索树（BST） 和 堆（Heap） 的性质。它由法国数学家笛卡尔（René Descartes）的名字命名，但实际上是由 Vuillmin 在解决范围搜索的几何问题时提出的。

笛卡尔树可用于高效地解决 区间最值查询（RMQ, Range Minimum/Maximum Query） 问题，也可以用于寻找数组中每个元素左边或右边第一个比它大/小的元素等问题。当然还有其他妙用，下面将会给出例题。

另外，给出宝藏教学视频链接 算法讲解151【扩展】有序表专题4-笛卡尔树、Treap树

1. 核心定义与性质

给定一个序列 A=[a1,a2,…,an]A = [a_1, a_2, \dots, a_n]（假设所有元素互不相同），其对应的笛卡尔树是一棵二叉树，满足以下两个关键性质：

  1. 二叉搜索树性质（针对下标key）：

    • 树中的每个节点对应原序列中的一个元素 aia_i。
    • 如果我们按照节点的下标 ii 进行中序遍历（In-order Traversal），得到的序列正好是原序列的下标顺序 1,2,…,n1, 2, \dots, n。
    • 这意味着：对于任意节点 uu（对应下标 ii），其左子树中所有节点的下标都小于 ii，右子树中所有节点的下标都大于 ii。

  2. 堆性质（针对数值value）：

    • 如果我们按照节点的数值 aia_i 来看，整棵树满足堆的性质。
    • 通常构建为小根堆（父节点的值 ≤\le 子节点的值），此时根节点是整个序列的最小值。
    • 也可以构建为大根堆（父节点的值 ≥\ge 子节点的值），此时根节点是整个序列的最大值。

结论： 如果序列中的元素互不相同，那么该序列对应的笛卡尔树是唯一的。

2. 直观理解

想象你有一个数组，你要把它变成一棵树：

  • 根节点一定是整个数组中的最小值（如果是小根堆）。
  • 这个最小值把数组分成了左右两部分（左边下标比它小，右边下标比它大）。
  • 左子树就是由左边这部分数组递归构建而成的笛卡尔树。
  • 右子树就是由右边这部分数组递归构建而成的笛卡尔树。

例如，对于序列 [3, 1, 6, 4, 5, 2]：

  1. 最小值是 1（下标1），它是根。
  2. 左边是 [3]，构建左子树，根是 3。
  3. 右边是 [6, 4, 5, 2]，最小值是 2（下标5），作为右子树的根。
  4. 2 的左边是 [6, 4, 5]，最小值 4，以此类推。

3. 构建算法

笛卡尔树可以在 O(n)O(n) 的线性时间内构建完成，这比普通的 O(nlog⁡n)O(n \log n) 排序或 O(n2)O(n^2) 的递归构建要快得多。最常用的方法是利用单调栈。

算法流程（以小根堆为例）：

我们按顺序遍历数组中的每个元素 aia_i，维护一条从根节点一直向右走的链（称为右链）。这条右链上的节点值是自上而下递增的（因为要满足堆性质，且新来的元素下标最大，只能在右边）。

当插入新元素 aia_i 时：

  1. 比较： 从右链的最底端（当前最右下角的节点）开始向上找，找到第一个值小于 aia_i 的节点 uu。
  2. 调整：
    • 节点 uu 原来的右孩子（如果有），将成为 aia_i 的左孩子。这是因为 aia_i 的下标比 uu 大，但比 uu 原来的右孩子大，且 aia_i 的值比 uu 原来的右孩子小（否则早就被弹出了），所以 aia_i 应该插在 uu 和它原来的右孩子之间。
    • 将 aia_i 设为 uu 的右孩子。
  3. 栈操作： 在单调栈中，弹出所有值大于 aia_i 的节点，最后将 aia_i 压入栈。栈中保存的正是当前的右链。

代码展示：

#include <bits/stdc++.h>

struct node {
    int l, r;
};

int stk[N], top;

signed main() {
    init();
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::vector<node> tr(n + 1);
    for (int i = 1, cur; i <= n; i++) {
        cur = top;
        while (cur && a[stk[cur]] > a[i]) cur--;
        if (cur) tr[stk[cur]].r = i;
        if (top > cur) tr[i].l = stk[cur + 1];
        top = cur + 1;
        stk[top] = i;
    }
    return 0;
}

4. 主要应用

笛卡尔树最强大的地方在于它将区间问题转化为了树上的路径问题。

  1. 区间最值查询 (RMQ)：

    • 在笛卡尔树（小根堆）中，原序列区间 [L,R][L, R] 的最小值，恰好是该区间对应节点集合的最近公共祖先（LCA）。
    • 因为 LCA 的值一定小于等于其子树中所有节点的值，且由于 BST 性质，LCA 的下标一定在 [L,R][L, R] 之间。
    • 这使得 RMQ 问题可以转化为 LCA 问题，进而可以使用 O(1)O(1) 或 O(log⁡n)O(\log n) 的算法解决。

  2. 寻找左右边界：

    • 对于每个元素 aia_i，它在笛卡尔树中的左孩子通常是它左边第一个比它大的元素（在大根堆情况下）或者相关的边界信息。
    • 更准确地说，通过笛卡尔树可以快速确定以 aia_i 为最小值的最大区间范围（即向左延伸到哪个位置，向右延伸到哪个位置）。这在解决“直方图中最大矩形”等经典问题时非常有用。

  3. 动态规划优化：

    • 在某些区间 DP 问题中，如果转移方程依赖于区间最值的位置，笛卡尔树可以提供一种分治的策略（类似笛卡尔树分治），将复杂度从 O(n2)O(n^2) 降低到 O(nlog⁡n)O(n \log n) 甚至 O(n)O(n)。

  4. Treap 的特例：

    • 著名的平衡树 Treap (Tree + Heap) 本质上就是一棵笛卡尔树。在 Treap 中，关键字（Key）满足 BST 性质，而优先级（Priority）是随机生成的并满足堆性质。如果我们将序列的下标看作 Key，序列的值看作 Priority，那么笛卡尔树就是一个确定的 Treap。

5. 例题

这些例题都是视频中讲了的，更多的分析我就不写了。

  1. P1377 [TJOI2011] 树的序
    其实问题很容易解决，构建好搜索二叉树后先序遍历即可，问题在于如何 O(n)O(n) 构建搜索二叉树，而这就是笛卡尔树的一种用处。做法为将插入的值作为笛卡尔树的key满足二叉搜索树性质，将插入的顺序作为value，满足小根堆的性质，这样构建出来的笛卡尔树的形态将和朴素算法构建的平衡二叉树形态一致。

    #include <bits/stdc++.h>
constexpr int N = 1e5 + 10;

int stk[N], top;

struct node {
    int l, r;
};

signed main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) b[a[i]] = i;
    std::vector<node> tr(n + 1);
    for (int i = 1; i <= n; i++) {
        int cur = top;
        while (cur && b[stk[cur]] > b[i]) cur--;
        if (cur) tr[stk[cur]].r = i;
        if (top > cur) tr[i].l = stk[cur + 1];
        top = cur + 1;
        stk[top] = i;
    }
    top = 1;
    while (top) {
        const int t = stk[top--];
        std::cout << t << " ";
        if (tr[t].r) stk[++top] = tr[t].r;
        if (tr[t].l) stk[++top] = tr[t].l;
    }
    return 0;
}

  2. E. Yet Another Array Counting Problem

    #include <bits/stdc++.h>
#define int long long
constexpr int N = 2e5 + 10, mod = 1e9 + 7;

int stk[N], top;

struct node {
    int l, r;
};

signed main() {
    int T;
    std::cin >> T;
    while (T--) {
        int n, m;
        std::cin >> n >> m;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        std::vector<node> tr(n + 1);
        top = 0;
        for (int i = 1, cur; i <= n; i++) {
            cur = top;
            while (cur && a[stk[cur]] < a[i]) cur--;
            if (cur) tr[stk[cur]].r = i;
            if (top > cur) tr[i].l = stk[cur + 1];
            top = cur + 1;
            stk[top] = i;
        }
        std::vector dp(n + 1, std::vector<int>(m + 1));
        for (int i = 0; i <= m; i++) dp[0][i] = 1;
        auto dfs = [&](auto&& self, const int x) -> void {
            if (!x) return;
            self(self, tr[x].l);
            self(self, tr[x].r);
            std::vector<int> tmp(m + 1);
            for (int i = 1; i <= m; i++) {
                tmp[i] = dp[tr[x].l][i - 1] * dp[tr[x].r][i] % mod;
            }
            for (int i = 1; i <= m; i++) {
                dp[x][i] = (dp[x][i - 1] + tmp[i]) % mod;
            }
        };
        dfs(dfs, stk[1]);
        std::cout << dp[stk[1]][m] << "\n";
    }
    return 0;
}

  3. P6453 [COCI 2008/2009 #4] PERIODNI

    #include <bits/stdc++.h>
#define int long long
constexpr int mod = 1e9 + 7, N = 550, M = 1e6 + 1;

struct node {
    int l, r;
};

int stk[N], top;
int fac[M], inv[M];

int ksm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i < M; i++) fac[i] = fac[i - 1] * i % mod;
    inv[M - 1] = ksm(fac[M - 1], mod - 2);
    for (int i = M - 2; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}

int C(const int n, const int m) {
    if (n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main() {
    init();
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::vector<node> tr(n + 1);
    for (int i = 1, cur; i <= n; i++) {
        cur = top;
        while (cur && a[stk[cur]] > a[i]) cur--;
        if (cur) tr[stk[cur]].r = i;
        if (top > cur) tr[i].l = stk[cur + 1];
        top = cur + 1;
        stk[top] = i;
    }
    std::vector dp(n + 1, std::vector<int>(k + 1));
    dp[0][0] = 1;
    std::vector<int> siz(n + 1);
    auto dfs = [&](auto&& self, const int u, const int fa) -> void {
        if (!u) return;
        self(self, tr[u].l, u);
        self(self, tr[u].r, u);
        siz[u] = siz[tr[u].l] + siz[tr[u].r] + 1;
        std::vector<int> tmp(k + 1);
        for (int l = 0; l <= std::min(k, siz[tr[u].l]); l++) {
            for (int r = 0; r <= std::min(k - l, siz[tr[u].r]); r++) {
                tmp[l + r] = (tmp[l + r] + dp[tr[u].l][l] * dp[tr[u].r][r] % mod) % mod;
            }
        }

        for (int i = 0; i <= std::min(siz[u], k); i++) {
            for (int j = 0; j <= i; j++) {
                dp[u][i] = (dp[u][i] + C(siz[u] - j, i - j) *
                    C(a[u] - a[fa], i - j) % mod * fac[i - j] % mod * tmp[j] % mod) % mod;
            }
        }
    };
    dfs(dfs, stk[1], 0);
    std::cout << dp[stk[1]][k] << "\n";
    return 0;
}

最后更新于：2026-03-25

最近更新:
贡献者: 杨必胜