笛卡尔树—简介

笛卡尔树是堆与二叉查找树的结合版本。所以他当然是一棵二叉树，然后又具有小根堆的性质。

每一个节点有一个键值二元组组成$(k,w)$构成。如果笛卡尔树的$(k,w)$是确定的，那么笛卡尔树的结构是惟一的。

其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值$k$恰好对应数组下标，这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是连续的一个区间（这样才能满足二叉搜索树的性质）。更一般的情况则是任意二元组构建的笛卡尔树。

构建

始终维护右链(即图中红色框中的链)，可以用栈来维护，也可以直接从链的最后一个节点开始往前逐步枚举(则需要记录一个father数组)，二者是等价的。

一直枚举直到出现一个小于自己的节点，然后考虑接在这个节点的右儿子处，如果不行，则将该节点及其子树全部作为新节点的左儿子。

用栈来建树

for (int i = 1; i <= n; i++) {
  int k = top;
  while (k > 0 && h[stk[k]] > h[i]) k--;
  if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
  if (k < top) ls[i] = stk[k + 1];  // ls代表笛卡尔树每个节点的左儿子
  stk[++k] = i;
  top = k;
}
1
2
3
4
5
6
7
8

用father来建树

int cartesian_build(int n) {  // 建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}
1
2
3
4
5
6
7
8
9
10
11

应用

经典例题：HDU 1509最大子矩形

题目大意： $n$个位置，每个位置上的高度是$h_i$，求最大子矩阵。

可用单调栈完成。

我们把下标作为键值$k$，$h_i$作为键值$w$满足小根堆性质，构建一棵 $(i,h_i)$的笛卡尔树。答案为该点的$w$乘子树大小(表示长度，由于其连续的性质)。也可以在$O(n)$内完成。

参考代码(来自OI-WIKI)：

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node {
  int idx, val, par, ch[2];

  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];
ll ans;

int cartesian_build(int n) {  // 建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}

int dfs(int x) {  // 一次dfs更新答案就可以了
  if (!x) return 0;
  int sz = dfs(tree[x].ch[0]);
  sz += dfs(tree[x].ch[1]);
  ans = max(ans, (ll)(sz + 1) * tree[x].val);
  return sz + 1;
}

int main() {
  int n, hi;
  while (scanf("%d", &n), n) {
    tree[0].init(0, 0, 0);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &hi);
      tree[i].init(i, hi, 0);
    }
    root = cartesian_build(n);
    ans = 0;
    dfs(root);
    printf("%lld\n", ans);
  }
  return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56