前往 算竞题解 分类 || 前往 算竞模板 分类

简介

下面介绍一种不常用但是经常被提起的数据结构 —— 笛卡尔树，可以说是平衡树的入门基础。

笛卡尔树既满足二叉搜索树又满足堆，即对于任意键值对 {k,v}\{k,v\}，max⁡{kl}<k<min⁡{kr}\max\{k_l\} < k < \min\{k_r\} 且 max⁡{vl}≥v≤max⁡{vr}\max\{v_l\} \ge v \le \max\{v_r\}，其中 {kl}\{k_l\} 表示左子树中的所有 kk。

由于笛卡尔树能解决的问题很多都能通过单调栈解决，因此笛卡尔树很少用。

模板题链接

洛谷 P3369 【模板】普通平衡树

HDU 1506 Largest Rectangle in a Histogram （不止一种解法哦）

核心思想

首先我们需要按 kk 将键值对排序，假设我们将索引当作 kk 则序列就是已排序的。从左往右遍历即可 O(n)O(n) 完成笛卡尔树的建立，使用单调栈维护一个前缀升序关系。假设现将 xx 插入单调栈，压在其下方的是 yy（即前缀最近小于），最近出栈的元素是 zz，只需将 xx 作为 yy 的右儿子，将 zz 作为 xx 的左儿子即可插入两者之间即可。

完整代码

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
// Jamhus Tao / GreatLiangpi
// Start at 2022/10/6
// Please using int32_t and int64_t to replace the int and long long.
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
#pragma GCC optimize(3, "Ofast", "inline")
using namespace std;

// 笛卡尔树 - Useless
// 唯一且即是二叉搜索树又是堆, 这里以小顶堆为例
const int MAX = 10000005;
const int INF = 0x3f3f3f3f3f3f3f3fll;

struct CartTree {
    int val;      // 值
    int next[2];  // 子节点
} tr[MAX];
int root = 0;

// 建树, 1-index. 时间: O(n)
int a[MAX];
int stk[MAX];
int cnt_stk = 0;
void build(int n) {
    a[0] = -INF - 1;
    stk[cnt_stk++] = 0;
    for (int i = 1; i <= n; i++) {
        int tmp = cnt_stk;
        while (cnt_stk and a[stk[cnt_stk - 1]] > a[i])
            cnt_stk--;
        tr[stk[cnt_stk - 1]].next[1] = i;
        if (cnt_stk < tmp)
            tr[i].next[0] = stk[cnt_stk];
        stk[cnt_stk++] = i;
        tr[i].val = a[i];
    }
    root = tr[0].next[1];
}