跳转至

笛卡爾樹

引入

本文介紹一種不太常用，但是與大家熟知的平衡樹與堆密切相關的數據結構——笛卡爾樹。

笛卡爾樹是一種二叉樹，每一個結點由一個鍵值二元組 \((k,w)\) 構成。要求 \(k\) 滿足二叉搜索樹的性質，而 \(w\) 滿足堆的性質。一個有趣的事實是，如果笛卡爾樹的 \(k,w\) 鍵值確定，且 \(k\) 互不相同，\(w\) 互不相同，那麼這個笛卡爾樹的結構是唯一的。上圖：

eg

（圖源自維基百科）

上面這棵笛卡爾樹相當於把數組元素值當作鍵值 \(w\)，而把數組下標當作鍵值 \(k\)。顯然可以發現，這棵樹的鍵值 \(k\) 滿足二叉搜索樹的性質，而鍵值 \(w\) 滿足小根堆的性質。

其實圖中的笛卡爾樹是一種特殊的情況，因為二元組的鍵值 \(k\) 恰好對應數組下標，這種特殊的笛卡爾樹有一個性質，就是一棵子樹內的下標是連續的一個區間（這樣才能滿足二叉搜索樹的性質）。更一般的情況則是任意二元組構建的笛卡爾樹。

構建

棧構建

過程

我們考慮將元素按照鍵值 \(k\) 排序。然後一個一個插入到當前的笛卡爾樹中。那麼每次我們插入的元素必然在這個樹的右鏈（右鏈：即從根結點一直往右子樹走，經過的結點形成的鏈）的末端。於是我們執行這樣一個過程，從下往上比較右鏈結點與當前結點 \(u\) 的 \(w\)，如果找到了一個右鏈上的結點 \(x\) 滿足 \(x_w<u_w\)，就把 \(u\) 接到 \(x\) 的右兒子上，而 \(x\) 原本的右子樹就變成 \(u\) 的左子樹。

具體不解釋，我們直接上圖。圖中紅色框框部分就是我們始終維護的右鏈：

build

顯然每個數最多進出右鏈一次（或者説每個點在右鏈中存在的是一段連續的時間）。這個過程我們可以用棧維護，棧中維護當前笛卡爾樹的右鏈上的結點。一個點不在右鏈上了就把它彈掉。這樣每個點最多進出一次，複雜度 \(O(n)\)。

實現

偽代碼如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
新建一個大小為 n 的空棧。用 top 來標操作前的棧頂，k 來標記當前棧頂。
For i := 1 to n
    k := top
    While 棧非空 且 棧頂元素 > 當前元素 
        k--
    if 棧非空
        棧頂元素.右兒子 := 當前元素
    if k < top
        當前元素.左兒子 := 上一個被彈出的元素
    當前元素入棧
    top := k

1
2
3
4
5
6
7
8
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;
}

笛卡爾樹與 Treap

談到笛卡爾樹，很容易讓人想到一種家喻户曉的結構——Treap。沒錯，Treap 是笛卡爾樹的一種，只不過 \(w\) 的值完全隨機。Treap 也有線性的構建算法，如果提前將元素排好序，顯然可以使用上述單調棧算法完成構建過程，只不過很少會這麼用。

例題

HDU 1506 最大子矩形

題目大意：\(n\) 個位置，每個位置上的高度是 \(h_i\)，求最大子矩陣。舉一個例子，如下圖：

eg

陰影部分就是圖中的最大子矩陣。

這道題你可 DP，可單調棧，但你萬萬沒想到的是它也可以笛卡爾樹！具體地，我們把下標作為鍵值 \(k\)，\(h_i\) 作為鍵值 \(w\) 滿足小根堆性質，構建一棵 \((i,h_i)\) 的笛卡爾樹。

這樣我們枚舉每個結點 \(u\)，把 \(u_w\)（即結點 \(u\) 的高度鍵值 \(h\)）作為最大子矩陣的高度。由於我們建立的笛卡爾樹滿足小根堆性質，因此 \(u\) 的子樹內的結點的高度都大於等於 \(u\)。而我們又知道 \(u\) 子樹內的下標是一段連續的區間。於是我們只需要知道子樹的大小，然後就可以算這個區間的最大子矩陣的面積了。用每一個點計算出來的值更新答案即可。顯然這個可以一次 DFS 完成，因此複雜度仍是 \(O(n)\) 的。

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}

參考資料

維基百科 - 笛卡爾樹

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：sshwy, zhouyuyang2002, StudyingFather, Ir1d, ouuan, Enter-tainer
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用