笛卡尔树（Cartesian Tree）

What · 是什么

笛卡尔树是每个节点由二元组 (k, w) 构成的二叉树：k 满足二叉搜索树（BST）性质，w 满足堆性质。若所有 k 与 w 都互不相同，则结构唯一。竞赛中典型取法：数组下标为 k（BST 键），数组值为 w（小根堆权）——此时每棵子树对应原数组的一个连续区间，且子树根是该区间的值最小的元素。构建可用单调栈 O(n) 完成。重要推论：区间 [l,r] 的最小值 = 下标 l 与 r 在笛卡尔树上的 LCA 的值，于是 RMQ 可转成 O(1) 的树上 LCA 查询。Treap 本质是 k 有序、w 随机的笛卡尔树。

Why · 为什么

How · 实现

伪代码

# 单调栈 O(n) 构建（下标 1..n，值 w[]，小根堆）
stk = []
for i in 1..n:
    k = len(stk)
    while k > 0 and w[stk[k-1]] > w[i]: k -= 1
    if k > 0: rs[stk[k-1]] = i        # 右链上找到更小的祖先，i 为右儿子
    if k < len(stk): ls[i] = stk[k]   # i 的左儿子 = 被弹掉的栈顶
    stk = stk[:k] + [i]
root = stk[0]

Python 实现

def build_cartesian(w):
    """按值构建小根堆笛卡尔树（下标即 BST 键）。
    返回 (left[], right[])；下标 0..n-1。"""
    n = len(w)
    left = [-1] * n
    right = [-1] * n
    stk = []
    for i in range(n):
        last = -1
        while stk and w[stk[-1]] > w[i]:
            last = stk.pop()
        if stk:
            right[stk[-1]] = i
        if last != -1:
            left[i] = last
        stk.append(i)
    return left, right, stk[0]

def build_lca_binary_lifting(left, right, root):
    """简单倍增 LCA（仅供自测；竞赛 O(1) 可用欧拉序+ST 表）"""
    n = len(left)
    parent = [-1] * n
    for i in range(n):
        if left[i] != -1:
            parent[left[i]] = i
        if right[i] != -1:
            parent[right[i]] = i
    LOG = max(1, n.bit_length())
    up = [[-1] * n for _ in range(LOG)]
    up[0] = parent[:]
    for k in range(1, LOG):
        for v in range(n):
            mid = up[k - 1][v]
            up[k][v] = up[k - 1][mid] if mid != -1 else -1
    depth = [-1] * n
    stack = [(root, 0)]
    while stack:
        v, d = stack.pop()
        depth[v] = d
        for c in (left[v], right[v]):
            if c != -1:
                stack.append((c, d + 1))
    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        diff = depth[a] - depth[b]
        bit = 0
        while diff:
            if diff & 1:
                a = up[bit][a]
            diff >>= 1
            bit += 1
        if a == b:
            return a
        for k in range(LOG - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]; b = up[k][b]
        return parent[a]
    return lca

def cartesian_rmq_check():
    import random
    for _ in range(50):
        n = random.randint(1, 30)
        a = [random.randint(1, 100) for _ in range(n)]
        left, right, root = build_cartesian(a)
        # 验证 BST 结构：中序遍历 = 原下标顺序
        order = []
        def dfs(u):
            if u == -1:
                return
            dfs(left[u]); order.append(u); dfs(right[u])
        dfs(root)
        assert order == list(range(n))
        # 验证堆性质
        ok = True
        for i in range(n):
            for c in (left[i], right[i]):
                if c != -1 and a[c] < a[i]:
                    ok = False
        assert ok
        # 验证 RMQ 等价性（随机区间）
        lca = build_lca_binary_lifting(left, right, root)
        for _ in range(20):
            l = random.randint(0, n - 1)
            r = random.randint(l, n - 1)
            mn = min(a[l:r + 1])
            got = a[lca(l, r)]
            assert got == mn, (a, l, r, got, mn)
    print('cartesian tree RMQ equivalence OK (50 random cases)')

if __name__ == '__main__':
    left, right, root = build_cartesian([3, 2, 1, 6, 0, 5])
    print('root =', root)
    assert root == 4  # 值 0 最小
    cartesian_rmq_check()

易错点

• 构建时弹栈条件方向（小根堆用 >，大根堆用 <）写反会得到错误结构
• 新节点接右儿子前必须确保栈内仍有元素，k==0 时不可接
• 弹出的栈顶是左儿子、未弹出的栈顶是父节点——两者都不可少，漏一步树就断
• RMQ 转化取的是 LCA 的『值』不是下标（虽然本实现下标即值索引）
• 多个相等 w 时结构不唯一，需预先用稳定性或约定处理

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/cartesian-tree.md
• OI Wiki✓ https://oi-wiki.org/ds/cartesian-tree/