跳转至

左偏樹

什麼是左偏樹？

左偏樹 與 配對堆 一樣，是一種 可並堆，具有堆的性質，並且可以快速合併。

dist 的定義和性質

對於一棵二叉樹，我們定義 外節點 為左兒子或右兒子為空的節點，定義一個外節點的 \(\mathrm{dist}\) 為 \(1\)，一個不是外節點的節點 \(\mathrm{dist}\) 為其到子樹中最近的外節點的距離加一。空節點的 \(\mathrm{dist}\) 為 \(0\)。

注：很多其它教程中定義的 \(\mathrm{dist}\) 都是本文中的 \(\mathrm{dist}\) 減去 \(1\)，本文這樣定義是因為代碼寫起來方便。

一棵有 \(n\) 個節點的二叉樹，根的 \(\mathrm{dist}\) 不超過 \(\left\lceil\log (n+1)\right\rceil\)，因為一棵根的 \(\mathrm{dist}\) 為 \(x\) 的二叉樹至少有 \(x-1\) 層是滿二叉樹，那麼就至少有 \(2^x-1\) 個節點。注意這個性質是所有二叉樹都具有的，並不是左偏樹所特有的。

左偏樹的定義和性質

左偏樹是一棵二叉樹，它不僅具有堆的性質，並且是「左偏」的：每個節點左兒子的 \(\mathrm{dist}\) 都大於等於右兒子的 \(\mathrm{dist}\)。

因此，左偏樹每個節點的 \(\mathrm{dist}\) 都等於其右兒子的 \(\mathrm{dist}\) 加一。

需要注意的是，\(\mathrm{dist}\) 不是深度，左偏樹的深度沒有保證，一條向左的鏈也是左偏樹。

核心操作：合併（merge）

合併兩個堆時，由於要滿足堆性質，先取值較小（為了方便，本文討論小根堆）的那個根作為合併後堆的根節點，然後將這個根的左兒子作為合併後堆的左兒子，遞歸地合併其右兒子與另一個堆，作為合併後的堆的右兒子。為了滿足左偏性質，合併後若左兒子的 \(\mathrm{dist}\) 小於右兒子的 \(\mathrm{dist}\)，就交換兩個兒子。

參考代碼：

實現 
1
2
3
4
5
6
7
8
9
int merge(int x, int y) {
  if (!x || !y) return x | y;  // 若一個堆為空則返回另一個堆
  if (t[x].val > t[y].val) swap(x, y);  // 取值較小的作為根
  t[x].rs = merge(t[x].rs, y);          // 遞歸合併右兒子與另一個堆
  if (t[t[x].rs].d > t[t[x].ls].d)
    swap(t[x].ls, t[x].rs);   // 若不滿足左偏性質則交換左右兒子
  t[x].d = t[t[x].rs].d + 1;  // 更新dist
  return x;
}

由於左偏性質，每遞歸一層，其中一個堆根節點的 \(\mathrm{dist}\) 就會減小 \(1\)，而「一棵有 \(n\) 個節點的二叉樹，根的 \(\mathrm{dist}\) 不超過 \(\left\lceil\log (n+1)\right\rceil\)」，所以合併兩個大小分別為 \(n\) 和 \(m\) 的堆複雜度是 \(O(\log n+\log m)\)。

左偏樹還有一種無需交換左右兒子的寫法：將 \(\mathrm{dist}\) 較大的兒子視作左兒子，\(\mathrm{dist}\) 較小的兒子視作右兒子：

實現 
1
2
3
4
5
6
7
8
9
int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  rs(x) = merge(rs(x), y);
  t[x].d = t[rs(x)].d + 1;
  return x;
}

左偏樹的其它操作

插入節點

單個節點也可以視為一個堆，合併即可。

刪除根

合併根的左右兒子即可。

刪除任意節點

做法

先將左右兒子合併，然後自底向上更新 \(\mathrm{dist}\)、不滿足左偏性質時交換左右兒子，當 \(\mathrm{dist}\) 無需更新時結束遞歸：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

// 有了 pushup，直接 merge 左右兒子就實現了刪除節點並保持左偏性質
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  t[rs(x) = merge(rs(x), y)].fa = x;
  pushup(x);
  return x;
}

void pushup(int x) {
  if (!x) return;
  if (t[x].d != t[rs(x)].d + 1) {
    t[x].d = t[rs(x)].d + 1;
    pushup(t[x].fa);
  }
}

複雜度證明

我們令當前 pushup 的這個節點為 \(x\)，其父親為 \(y\)，一個節點的「初始 \(\mathrm{dist}\)」為它在 pushup 前的 \(\mathrm{dist}\)。我們先 pushup 一下刪除的節點，然後從其父親開始起討論複雜度。

繼續遞歸下去有兩種情況：

  1. \(x\) 是 \(y\) 的右兒子，此時 \(y\) 的初始 \(\mathrm{dist}\) 為 \(x\) 的初始 \(\mathrm{dist}\) 加一。
  2. \(x\) 是 \(y\) 的左兒子，只有 \(y\) 的左右兒子初始 \(\mathrm{dist}\) 相等時（此時左兒子 \(\mathrm{dist}\) 減一會導致左右兒子互換）才會繼續遞歸下去，因此 \(y\) 的初始 \(\mathrm{dist}\) 仍然是 \(x\) 的初始 \(\mathrm{dist}\) 加一。

所以，我們得到，除了第一次 pushup（因為被刪除節點的父親的初始 \(\mathrm{dist}\) 不一定等於被刪除節點左右兒子合併後的初始 \(\mathrm{dist}\) 加一），每遞歸一層 \(x\) 的初始 \(\mathrm{dist}\) 就會加一，因此最多遞歸 \(O(\log n)\) 層。

整個堆加上/減去一個值、乘上一個正數

其實可以打標記且不改變相對大小的操作都可以。

在根打上標記，刪除根/合併堆（訪問兒子）時下傳標記即可：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  pushdown(x);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int pop(int x) {
  pushdown(x);
  return merge(t[x].ls, t[x].rs);
}

隨機合併

直接貼上代碼

實現 
1
2
3
4
5
6
7
8
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[y].val < t[x].val) swap(x, y);
  if (rand() & 1)  // 隨機選擇是否交換左右子節點
    swap(t[x].ls, t[x].rs);
  t[x].ls = merge(t[x].ls, y);
  return x;
}

可以看到該實現方法唯一不同之處便是採用了隨機數來實現合併，這樣一來便可以省去 \(\mathrm{dist}\) 的相關計算。且平均時間複雜度亦為 \(O(\log n)\)，詳細證明可參考 Randomized Heap。

例題

模板題

luogu P3377【模板】左偏樹（可並堆）

Monkey King

羅馬遊戲

需要注意的是：

  1. 合併前要檢查是否已經在同一堆中。

  2. 左偏樹的深度可能達到 \(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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>

using namespace std;

int read() {  // 快读
  int out = 0;
  char c;
  while (!isdigit(c = getchar()))
    ;
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out;
}

const int N = 1000010;

struct Node {
  int val, ch[2], d;
} t[N];

int& rs(int x);
int merge(int x, int y);

int find(int x);

int n, m, f[N];
bool kill[N];
char op[10];

int main() {
  int i, x, y;

  n = read();

  for (i = 1; i <= n; ++i) {
    t[i].val = read();
    f[i] = i;
  }

  m = read();

  while (m--) {
    scanf("%s", op);
    if (op[0] == 'M') {
      x = read();
      y = read();
      if (kill[x] || kill[y] || find(x) == find(y)) continue;  // 这是题意
      f[find(x)] = f[find(y)] = merge(find(x), find(y));
    } else {
      x = read();
      if (!kill[x]) {
        x = find(x);
        kill[x] = true;
        f[x] = f[t[x].ch[0]] = f[t[x].ch[1]] = merge(t[x].ch[0], t[x].ch[1]);
        // 由于堆中的点会 find 到 x，所以 f[x] 也要修改
        printf("%d\n", t[x].val);
      } else
        puts("0");
    }
  }

  return 0;
}

int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {  // 左偏树并堆
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  rs(x) = merge(rs(x), y);
  t[x].d = t[rs(x)].d + 1;
  return x;
}

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }  // 查找

樹上問題

「APIO2012」派遣

「JLOI2015」城池攻佔

這類題目往往是每個節點維護一個堆，與兒子合併，依題意彈出、修改、計算答案，有點像線段樹合併的類似題目。

城池攻佔參考代碼 
  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
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

ll read() {
  ll out = 0;
  int f = 1;
  char c;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') f = -1, c = getchar();
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out * f;
}

const int N = 300010;

struct Node {
  int ls, rs, d;
  ll val, add, mul;

  Node() {
    ls = rs = add = 0;
    d = mul = 1;
  }
} t[N];

int merge(int x, int y);
int pop(int x);
void madd(int u, ll x);
void mmul(int u, ll x);
void pushdown(int x);

void add(int u, int v);
void dfs(int u);

int head[N], nxt[N], to[N], cnt;
int n, m, p[N], f[N], a[N], dep[N], c[N], ans1[N],
    ans2[N];  // p是树上每个点对应的堆顶
ll h[N], b[N];

int main() {
  int i;

  n = read();
  m = read();

  for (i = 1; i <= n; ++i) h[i] = read();

  for (i = 2; i <= n; ++i) {
    f[i] = read();
    add(f[i], i);
    a[i] = read();
    b[i] = read();
  }

  for (i = 1; i <= m; ++i) {
    t[i].val = read();
    c[i] = read();
    p[c[i]] = merge(i, p[c[i]]);
  }

  dfs(1);

  for (i = 1; i <= n; ++i) printf("%d\n", ans1[i]);
  for (i = 1; i <= m; ++i) printf("%d\n", ans2[i]);

  return 0;
}

void dfs(int u) {
  int i, v;  // 根据题意开始dfs
  for (i = head[u]; i; i = nxt[i]) {
    v = to[i];
    dep[v] = dep[u] + 1;
    dfs(v);
  }
  while (p[u] && t[p[u]].val < h[u]) {
    ++ans1[u];
    ans2[p[u]] = dep[c[p[u]]] - dep[u];
    p[u] = pop(p[u]);
  }
  if (a[u])
    mmul(p[u], b[u]);
  else
    madd(p[u], b[u]);
  if (u > 1)
    p[f[u]] = merge(p[u], p[f[u]]);
  else
    while (p[u]) {
      ans2[p[u]] = dep[c[p[u]]] + 1;
      p[u] = pop(p[u]);
    }
}

void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
}

int merge(int x, int y) {  // 合并
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  pushdown(x);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int pop(int x) {
  pushdown(x);
  return merge(t[x].ls, t[x].rs);
}

void madd(int u, ll x) {
  t[u].val += x;
  t[u].add += x;
}

void mmul(int u, ll x) {
  t[u].val *= x;
  t[u].add *= x;
  t[u].mul *= x;
}

void pushdown(int x) {  // like 线段树，下传合并
  mmul(t[x].ls, t[x].mul);
  madd(t[x].ls, t[x].add);
  mmul(t[x].rs, t[x].mul);
  madd(t[x].rs, t[x].add);
  t[x].add = 0;
  t[x].mul = 1;
}

「SCOI2011」棘手的操作

首先，找一個節點所在堆的堆頂要用並查集，而不能暴力向上跳。

再考慮單點查詢，若用普通的方法打標記，就得查詢點到根路徑上的標記之和，最壞情況下可以達到 \(O(n)\) 的複雜度。如果只有堆頂有標記，就可以快速地查詢了，但如何做到呢？

可以用類似啓發式合併的方式，每次合併的時候把較小的那個堆標記暴力下傳到每個節點，然後把較大的堆的標記作為合併後的堆的標記。由於合併後有另一個堆的標記，所以較小的堆下傳標記時要下傳其標記減去另一個堆的標記。由於每個節點每被合併一次所在堆的大小至少乘二，所以每個節點最多被下放 \(O(\log n)\) 次標記，暴力下放標記的總複雜度就是 \(O(n\log n)\)。

再考慮單點加，先刪除，再更新，最後插入即可。

然後是全局最大值，可以用一個平衡樹/支持刪除任意節點的堆（如左偏樹）/multiset 來維護每個堆的堆頂。

所以，每個操作分別如下：

  1. 暴力下傳點數較小的堆的標記，合併兩個堆，更新 size、tag，在 multiset 中刪去合併後不在堆頂的那個原堆頂。
  2. 刪除節點，更新值，插入回來，更新 multiset。需要分刪除節點是否為根來討論一下。
  3. 堆頂打標記，更新 multiset。
  4. 打全局標記。
  5. 查詢值 + 堆頂標記 + 全局標記。
  6. 查詢根的值 + 堆頂標記 + 全局標記。
  7. 查詢 multiset 最大值 + 全局標記。
棘手的操作參考代碼 
  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
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
#include <set>

using namespace std;

int read() {
  int out = 0, f = 1;
  char c;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out * f;
}

const int N = 300010;

struct Node {
  int val, ch[2], d, fa;
} t[N];

int& rs(int x);
int merge(int x, int y);
void pushup(int x);
void pushdown(int x, int y);

int find(int x);

int n, m, f[N], tag[N], siz[N], delta;
char op[10];
multiset<int> s;

int main() {
  int i, x, y;

  n = read();

  for (i = 1; i <= n; ++i) {
    t[i].val = read();
    f[i] = i;
    siz[i] = 1;
    s.insert(t[i].val);
  }

  m = read();

  while (m--) {  // 根据题意处理具体看解法
    scanf("%s", op);
    if (op[0] == 'U') {
      x = find(read());
      y = find(read());
      if (x != y) {
        if (siz[x] > siz[y]) swap(x, y);
        pushdown(x, tag[x] - tag[y]);
        f[x] = f[y] = merge(x, y);
        if (f[x] == x) {
          s.erase(s.find(t[y].val + tag[y]));
          tag[x] = tag[y];
          siz[x] += siz[y];
          tag[y] = siz[y] = 0;
        } else {
          s.erase(s.find(t[x].val + tag[y]));
          siz[y] += siz[x];
          tag[x] = siz[x] = 0;
        }
      }
    } else if (op[0] == 'A') {
      if (op[1] == '1') {
        x = read();
        if (x == find(x)) {
          t[t[x].ch[0]].fa = t[t[x].ch[1]].fa = 0;
          y = merge(t[x].ch[0], t[x].ch[1]);
          s.erase(s.find(t[x].val + tag[x]));
          t[x].val += read();
          t[x].fa = t[x].ch[0] = t[x].ch[1] = 0;
          t[x].d = 1;
          f[x] = f[y] = merge(x, y);
          s.insert(t[f[x]].val + tag[x]);
          if (f[x] == y) {
            tag[y] = tag[x];
            siz[y] = siz[x];
            tag[x] = siz[x] = 0;
          }
        } else {
          t[t[x].ch[0]].fa = t[t[x].ch[1]].fa = t[x].fa;
          t[t[x].fa].ch[x == t[t[x].fa].ch[1]] = merge(t[x].ch[0], t[x].ch[1]);
          t[x].val += read();
          t[x].fa = t[x].ch[0] = t[x].ch[1] = 0;
          t[x].d = 1;
          y = find(x);
          f[x] = f[y] = merge(x, y);
          if (f[x] == x) {
            s.erase(s.find(t[y].val + tag[y]));
            s.insert(t[x].val + tag[y]);
            tag[x] = tag[y];
            siz[x] = siz[y];
            tag[y] = siz[y] = 0;
          }
        }
      } else if (op[1] == '2') {
        x = find(read());
        s.erase(s.find(t[x].val + tag[x]));
        tag[x] += read();
        s.insert(t[x].val + tag[x]);
      } else
        delta += read();
    } else {
      if (op[1] == '1') {
        x = read();
        printf("%d\n", t[x].val + tag[find(x)] + delta);
      } else if (op[1] == '2') {
        x = find(read());
        printf("%d\n", t[x].val + tag[x] + delta);
      } else
        printf("%d\n", *s.rbegin() + delta);
    }
  }

  return 0;
}

int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {  // 板子，合并
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  t[rs(x) = merge(rs(x), y)].fa = x;
  pushup(x);
  return x;
}

// 以下俩是一个东西
void pushup(int x) {
  if (!x) return;
  if (t[x].d != t[rs(x)].d + 1) {
    t[x].d = t[rs(x)].d + 1;
    pushup(t[x].fa);
  }
}

void pushdown(int x, int y) {
  if (!x) return;
  t[x].val += y;
  pushdown(t[x].ch[0], y);
  pushdown(t[x].ch[1], y);
}

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

「BOI2004」Sequence 數字序列

這是一道論文題，詳見 《黃源河 -- 左偏樹的特點及其應用》。

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