跳转至

析合樹

解釋一下本文可能用到的符號：\(\wedge\) 邏輯與，\(\vee\) 邏輯或。

關於段的問題

我們由一個小清新的問題引入：

對於一個 \(1-n\) 的排列，我們稱一個值域連續的區間為段。問一個排列的段的個數。比如，\(\{5 ,3 ,4, 1 ,2\}\) 的段有：\([1,1],[2,2],[3,3],[4,4],[5,5],[2,3],[4,5],[1,3],[2,5],[1,5]\)。

看到這個東西，感覺要維護區間的值域集合，複雜度好像挺不友好的。線段樹可以查詢某個區間是否為段，但不太能統計段的個數。

這裏我們引入這個神奇的數據結構——析合樹！

連續段

在介紹析合樹之前，我們先做一些前提條件的限定。鑑於 LCA 的課件中給出的定義不易理解，為方便讀者理解，這裏給出一些不太嚴謹（但更容易理解）的定義。

排列與連續段

排列：定義一個 \(n\) 階排列 \(P\) 是一個大小為 \(n\) 的序列，使得 \(P_i\) 取遍 \(1,2,\cdots,n\)。説得形式化一點，\(n\) 階排列 \(P\) 是一個有序集合滿足：

  1. \(|P|=n\).
  2. \(\forall i,P_i\in[1,n]\).

  3. \(\nexists i,j\in[1,n],P_i=P_j\).

    連續段：對於排列 \(P\)，定義連續段 \((P,[l,r])\) 表示一個區間 \([l,r]\)，要求 \(P_{l\sim r}\) 值域是連續的。説得更形式化一點，對於排列 \(P\)，連續段表示一個區間 \([l,r]\) 滿足：

\[ (\nexists\ x,z\in[l,r],y\notin[l,r],\ P_x<P_y<P_z) \]

特別地，當 \(l>r\) 時，我們認為這是一個空的連續段，記作 \((P,\varnothing)\)。

我們稱排列 \(P\) 的所有連續段的集合為 \(I_P\)，並且我們認為 \((P,\varnothing)\in I_P\)。

連續段的運算

連續段是依賴區間和值域定義的，於是我們可以定義連續段的交併差的運算。

定義 \(A=(P,[a,b]),B=(P,[x,y])\)，且 \(A,B\in I_P\)。於是連續段的關係和運算可以表示為：

  1. \(A\subseteq B\iff x\le a\wedge b\le y\).
  2. \(A=B\iff a=x\wedge b=y\).
  3. \(A\cap B=(P,[\max(a,x),\min(b,y)])\).
  4. \(A\cup B=(P,[\min(a,x),\max(b,y)])\).
  5. \(A\setminus B=(P,\{i|i\in[a,b]\wedge i\notin[x,y]\})\).

其實這些運算就是普通的集合交併差放在區間上而已。

連續段的性質

連續段的一些顯而易見的性質。我們定義 \(A,B\in I_P,A \cap B \neq \varnothing,A \notin B,B \notin A\)，那麼有 \(A\cup B,A\cap B,A\setminus B,B\setminus A\in I_P\)。

證明？證明的本質就是集合的交併差的運算。

析合樹

好的，現在講到重點了。你可能已經猜到了，析合樹正是由連續段組成的一棵樹。但是要知道一個排列可能有多達 \(O(n^2)\) 個連續段，因此我們就要抽出其中更基本的連續段組成析合樹。

本原段

其實這個定義全稱叫作 本原連續段。但筆者認為本原段更為簡潔。

對於排列 \(P\)，我們認為一個本原段 \(M\) 表示在集合 \(I_P\) 中，不存在與之相交且不包含的連續段。形式化地定義，我們認為 \(X\in I_P\) 且滿足 \(\forall A\in I_P,\ X\cap A= (P,\varnothing)\vee X\subseteq A\vee A\subseteq X\)。

所有本原段的集合為 \(M_P\). 顯而易見，\((P,\varnothing)\in M_P\)。

顯然，本原段之間只有相離或者包含關係。並且你發現 一個連續段可以由幾個互不相交的本原段構成。最大的本原段就是整個排列本身，它包含了其他所有本原段，因此我們認為本原段可以構成一個樹形結構，我們稱這個結構為 析合樹。更嚴格地説，排列 \(P\) 的析合樹由排列 \(P\) 的 所有本原段 組成。

前面幹講這麼多的定義，不來點圖怎麼行。考慮排列 \(P=\{9,1,10,3,2,5,7,6,8,4\}\). 它的本原段構成的析合樹如下：

p1

在圖中我們沒有標明本原段。而圖中 每個結點都代表一個本原段。我們只標明瞭每個本原段的值域。舉個例子，結點 \([5,8]\) 代表的本原段就是 \((P,[6,9])=\{5,7,6,8\}\)。於是這裏就有一個問題：什麼是析點合點？

析點與合點

這裏我們直接給出定義，稍候再來討論它的正確性。

  1. 值域區間：對於一個結點 \(u\)，用 \([u_l,u_r]\) 表示該結點的值域區間。
  2. 兒子序列：對於析合樹上的一個結點 \(u\)，假設它的兒子結點是一個 有序 序列，該序列是以值域區間為元素的（單個的數 \(x\) 可以理解為 \([x,x]\) 的區間）。我們把這個序列稱為兒子序列。記作 \(S_u\)。
  3. 兒子排列：對於一個兒子序列 \(S_u\)，把它的元素離散化成正整數後形成的排列稱為兒子排列。舉個例子，對於結點 \([5,8]\)，它的兒子序列為 \(\{[5,5],[6,7],[8,8]\}\)，那麼把區間排序標個號，則它的兒子排列就為 \(\{1,2,3\}\)；類似的，結點 \([4,8]\) 的兒子排列為 \(\{2,1\}\)。結點 \(u\) 的兒子排列記為 \(P_u\)。
  4. 合點：我們認為，兒子排列為順序或者逆序的點為合點。形式化地説，滿足 \(P_u=\{1,2,\cdots,|S_u|\}\) 或者 \(P_u=\{|S_u|,|S_u-1|,\cdots,1\}\) 的點稱為合點。葉子結點沒有兒子排列，我們也認為它是合點。
  5. 析點：不是合點的就是析點。

從圖中可以看到，只有 \([1,10]\) 不是合點。因為 \([1,10]\) 的兒子排列是 \(\{3,1,4,2\}\)。

析點與合點的性質

析點與合點的命名來源於他們的性質。首先我們有一個非常顯然的性質：對於析合樹中任何的結點 \(u\)，其兒子序列區間的並集就是結點 \(u\) 的值域區間。即 \(\bigcup_{i=1}^{|S_u|}S_u[i]=[u_l,u_r]\)。

對於一個合點 \(u\)：其兒子序列的任意 子區間 都構成一個 連續段。形式化地説，\(\forall S_u[l\sim r]\)，有 \(\bigcup_{i=l}^rS_u[i]\in I_P\)。

對於一個析點 \(u\)：其兒子序列的任意 長度大於 1（這裏的長度是指兒子序列中的元素數，不是下標區間的長度） 的子區間都 不 構成一個 連續段。形式化地説，\(\forall S_u[l\sim r],l<r\)，有 \(\bigcup_{i=l}^rS_u[i]\notin I_P\)。

合點的性質不難證明。因為合點的兒子排列要麼是順序，要麼是倒序，而值域區間也是首位相接，因此只要是連續的一段子序列（區間）都是一個連續段。

對於析點的性質可能很多讀者就不太能理解了：為什麼 任意 長度大於 \(1\) 的子區間都不構成連續段？

使用反證法。假設對於一個點 \(u\)，它的兒子序列中有一個 最長的 區間 \(S_u[l\sim r]\) 構成了連續段。那麼這個 \(A=\bigcup_{i=l}^rS_u[i]\in I_P\)，也就意味着 \(A\) 是一個本原段！（因為 \(A\) 是兒子序列中最長的，因此找不到一個與它相交又不包含的連續段）於是你就沒有使用所有的本原段構成這個析合樹。矛盾。

析合樹的構造

對於具體構造析合樹，LCA 提供了一種線性構造算法1，下面給出一種比較好懂的 \(O(n\log n)\) 算法。

增量法

我們考慮增量法。用一個棧維護前 \(i-1\) 個元素構成的析合森林。在這裏需要 着重強調，析合森林的意思是，在任何時侯，棧中結點要麼是析點要麼是合點。現在考慮當前結點 \(P_i\)。

  1. 我們先判斷它能否成為棧頂結點的兒子，如果能就變成棧頂的兒子，然後把棧頂取出，作為當前結點。重複上述過程直到棧空或者不能成為棧頂結點的兒子。
  2. 如果不能成為棧頂的兒子，就看能不能把棧頂的若干個連續的結點都合併成一個結點（判斷能否合併的方法在後面），把合併後的點，作為當前結點。
  3. 重複上述過程直到不能進行為止。然後結束此次增量，直接把當前結點壓棧。

接下來我們仔細解釋一下。

具體的策略

我們認為，如果當前點能夠成為棧頂結點的兒子，那麼棧頂結點是一個合點。如果是析點，那麼你合併後這個析點就存在一個子連續段，不滿足析點的性質。因此一定是合點。

如果無法成為棧頂結點的兒子，那麼我們就看棧頂連續的若干個點能否與當前點一起合併。設 \(l\) 為當前點所在區間的左端點。我們計算 \(L_i\) 表示右端點下標為 \(i\) 的連續段中，左端點 \(< l\) 的最大值。當前結點為 \(P_i\)，棧頂結點記為 \(t\)。

  1. 如果 \(L_i\) 不存在，那麼顯然當前結點無法合併；
  2. 如果 \(t_l=L_i\)，那麼這就是兩個結點合併，合併後就是一個 合點；
  3. 否則在棧中一定存在一個點 \(t'\) 的左端點 \({t'}_l=L_i\)，那麼一定可以從當前結點合併到 \(t’\) 形成一個 析點；

判斷能否合併

最後，我們考慮如何處理 \(L_i\)。事實上，一個連續段 \((P,[l,r])\) 等價於區間極差與區間長度 -1 相等。即

\[ \max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i=r-l \]

而且由於 P 是一個排列，因此對於任意的區間 \([l,r]\) 都有

\[ \max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i\ge r-l \]

於是我們就維護 \(\max_{l\le i\le r}P_i-\min_{l\le i\le r}P_i-(r-l)\)，那麼要找到一個連續段相當於查詢一個最小值！

有了上述思路，不難想到這樣的算法。對於增量過程中的當前的 \(i\)，我們維護一個數組 \(Q\) 表示區間 \([j,i]\) 的極差減長度。即

\[ Q_j=\max_{j\le k\le i}P_k-\min_{j\le k\le i}P_k-(i-j),\ \ 0<j<i \]

現在我們想知道在 \(1\sim i-1\) 中是否存在一個最小的 \(j\) 使得 \(Q_j=0\)。這等價於求 \(Q_{1\sim i-1}\) 的最小值。求得最小的 \(j\) 就是 \(L_i\)。如果沒有，那麼 \(L_i=i\)。

但是當第 \(i\) 次增量結束時，我們需要快速把 \(Q\) 數組更新到 i+1 的情況。原本的區間從 \([j,i]\) 變成 \([j,i+1]\)，如果 \(P_{i+1}>\max\) 或者 \(P_{i+1}<\min\) 都會造成 \(Q_j\) 發生變化。如何變化？如果 \(P_{i+1}>\max\)，相當於我們把 \(Q_j\) 先減掉 \(\max\) 再加上 \(P_{i+1}\) 就完成了 \(Q_j\) 的更新；\(P_{i+1}<\min\) 同理，相當於 \(Q_j=Q_j+\min-P_{i+1}\).

那麼如果對於一個區間 \([x,y]\)，滿足 \(P_{x\sim i},P_{x+1\sim i},P_{x+2\sim i},\cdots,P_{y\sim i}\) 的區間 \(\max\) 都相同呢？你已經發現了，那麼相當於我們在做一個區間加的操作；同理，當 \(P_{x\sim i},P_{x+1\sim i},\cdots,P_{y\sim i}\) 的區間 \(\min\) 都想同時也是一個區間加的操作。同時，\(\max\) 和 \(\min\) 的更新是相互獨立的，因此可以各自更新。

因此我們對 \(Q\) 的維護可以這樣描述：

  1. 找到最大的 \(j\) 使得 \(P_{j}>P_{i+1}\)，那麼顯然，\(P_{j+1\sim i}\) 這一段數全部小於 \(P_{i+1}\)，於是就需要更新 \(Q_{j+1\sim i}\) 的最大值。由於 \(P_{i},\max(P_i,P_{i-1}),\max(P_i,P_{i-1},P_{i-2}),\cdots,\max(P_i,P_{i-1},\cdots,P_{j+1})\) 是（非嚴格）單調遞增的，因此可以每一段相同的 \(\max\) 做相同的更新，即區間加操作。
  2. 更新 \(\min\) 同理。
  3. 把每一個 \(Q_j\) 都減 \(1\)。因為區間長度加 \(1\)。
  4. 查詢 \(L_i\)：即查詢 \(Q\) 的最小值的所在的 下標。

沒錯，我們可以使用線段樹維護 \(Q\)！現在還有一個問題：怎麼找到相同的一段使得他們的 \(\max/\min\) 都相同？使用單調棧維護！維護兩個單調棧分別表示 \(\max/\min\)。那麼顯然，棧中以相鄰兩個元素為端點的區間的 \(\max/\min\) 是相同的，於是在維護單調棧的時侯順便更新線段樹即可。

具體的維護方法見代碼。

講這麼多幹巴巴的想必小夥伴也聽得雲裏霧裏的，那麼我們就先上圖吧。長圖警告！

p2

實現

最後放一個實現的代碼供參考。代碼轉自 大米餅的博客，添加了一些註釋。

  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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <bits/stdc++.h>
#define rg register
using namespace std;
const int N = 200010;

int n, m, a[N], st1[N], st2[N], tp1, tp2, rt;
int L[N], R[N], M[N], id[N], cnt, typ[N], bin[20], st[N], tp;

// 本篇代碼原題應為 CERC2017 Intrinsic Interval
// a 數組即為原題中對應的排列
// st1 和 st2 分別兩個單調棧，tp1、tp2 為對應的棧頂，rt 為析合樹的根
// L、R 數組表示該析合樹節點的左右端點，M 數組的作用在析合樹構造時有提到
// id 存儲的是排列中某一位置對應的節點編號，typ 用於標記析點還是合點
// st 為存儲析合樹節點編號的棧，tp為其棧頂
struct RMQ {  // 預處理 RMQ（Max & Min）
  int lg[N], mn[N][17], mx[N][17];

  void chkmn(int& x, int y) {
    if (x > y) x = y;
  }

  void chkmx(int& x, int y) {
    if (x < y) x = y;
  }

  void build() {
    for (int i = bin[0] = 1; i < 20; ++i) bin[i] = bin[i - 1] << 1;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) mn[i][0] = mx[i][0] = a[i];
    for (int i = 1; i < 17; ++i)
      for (int j = 1; j + bin[i] - 1 <= n; ++j)
        mn[j][i] = min(mn[j][i - 1], mn[j + bin[i - 1]][i - 1]),
        mx[j][i] = max(mx[j][i - 1], mx[j + bin[i - 1]][i - 1]);
  }

  int ask_mn(int l, int r) {
    int t = lg[r - l + 1];
    return min(mn[l][t], mn[r - bin[t] + 1][t]);
  }

  int ask_mx(int l, int r) {
    int t = lg[r - l + 1];
    return max(mx[l][t], mx[r - bin[t] + 1][t]);
  }
} D;

// 維護 L_i

struct SEG {  // 線段樹
#define ls (k << 1)
#define rs (k << 1 | 1)
  int mn[N << 1], ly[N << 1];  // 區間加；區間最小值

  void pushup(int k) { mn[k] = min(mn[ls], mn[rs]); }

  void mfy(int k, int v) { mn[k] += v, ly[k] += v; }

  void pushdown(int k) {
    if (ly[k]) mfy(ls, ly[k]), mfy(rs, ly[k]), ly[k] = 0;
  }

  void update(int k, int l, int r, int x, int y, int v) {
    if (l == x && r == y) {
      mfy(k, v);
      return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if (y <= mid)
      update(ls, l, mid, x, y, v);
    else if (x > mid)
      update(rs, mid + 1, r, x, y, v);
    else
      update(ls, l, mid, x, mid, v), update(rs, mid + 1, r, mid + 1, y, v);
    pushup(k);
  }

  int query(int k, int l, int r) {  // 詢問 0 的位置
    if (l == r) return l;
    pushdown(k);
    int mid = (l + r) >> 1;
    if (!mn[ls])
      return query(ls, l, mid);
    else
      return query(rs, mid + 1, r);
    // 如果不存在 0 的位置就會自動返回當前你查詢的位置
  }
} T;

int o = 1, hd[N], dep[N], fa[N][18];

struct Edge {
  int v, nt;
} E[N << 1];

void add(int u, int v) {  // 樹結構加邊
  E[o] = (Edge){v, hd[u]};
  hd[u] = o++;
}

void dfs(int u) {
  for (int i = 1; bin[i] <= dep[u]; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int i = hd[u]; i; i = E[i].nt) {
    int v = E[i].v;
    dep[v] = dep[u] + 1;
    fa[v][0] = u;
    dfs(v);
  }
}

int go(int u, int d) {
  for (int i = 0; i < 18 && d; ++i)
    if (bin[i] & d) d ^= bin[i], u = fa[u][i];
  return u;
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  u = go(u, dep[u] - dep[v]);
  if (u == v) return u;
  for (int i = 17; ~i; --i)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}

// 判斷當前區間是否為連續段
bool judge(int l, int r) { return D.ask_mx(l, r) - D.ask_mn(l, r) == r - l; }

// 建樹
void build() {
  for (int i = 1; i <= n; ++i) {
    // 單調棧
    // 在區間 [st1[tp1-1]+1,st1[tp1]] 的最小值就是 a[st1[tp1]]
    // 現在把它出棧，意味着要把多減掉的 Min 加回來。
    // 線段樹的葉結點位置 j 維護的是從 j 到當前的 i 的
    // Max{j,i}-Min{j,i}-(i-j)
    // 區間加只是一個 Tag。
    // 維護單調棧的目的是輔助線段樹從 i-1 更新到 i。
    // 更新到 i 後，只需要查詢全局最小值即可知道是否有解

    while (tp1 && a[i] <= a[st1[tp1]])  // 單調遞增的棧，維護 Min
      T.update(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], a[st1[tp1]]), tp1--;
    while (tp2 && a[i] >= a[st2[tp2]])
      T.update(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], -a[st2[tp2]]), tp2--;

    T.update(1, 1, n, st1[tp1] + 1, i, -a[i]);
    st1[++tp1] = i;
    T.update(1, 1, n, st2[tp2] + 1, i, a[i]);
    st2[++tp2] = i;

    id[i] = ++cnt;
    L[cnt] = R[cnt] = i;  // 這裏的 L,R 是指節點所對應區間的左右端點
    int le = T.query(1, 1, n), now = cnt;
    while (tp && L[st[tp]] >= le) {
      if (typ[st[tp]] && judge(M[st[tp]], i)) {
        // 判斷是否能成為兒子，如果能就做
        R[st[tp]] = i, M[st[tp]] = L[now], add(st[tp], now), now = st[tp--];
      } else if (judge(L[st[tp]], i)) {
        typ[++cnt] = 1;  // 合點一定是被這樣建出來的
        L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now];
        // 這裏M數組是記錄節點最右面的兒子的左端點，用於上方能否成為兒子的判斷
        add(cnt, st[tp--]), add(cnt, now);
        now = cnt;
      } else {
        add(++cnt, now);  // 新建一個結點，把 now 添加為兒子
        // 如果從當前結點開始不能構成連續段，就合併。
        // 直到找到一個結點能構成連續段。而且我們一定能找到這樣
        // 一個結點。
        do add(cnt, st[tp--]);
        while (tp && !judge(L[st[tp]], i));
        L[cnt] = L[st[tp]], R[cnt] = i, add(cnt, st[tp--]);
        now = cnt;
      }
    }
    st[++tp] = now;  // 增量結束，把當前點壓棧

    T.update(1, 1, n, 1, i, -1);  // 因為區間右端點向後移動一格，因此整體 -1
  }

  rt = st[1];  // 棧中最後剩下的點是根結點
}

void query(int l, int r) {
  int x = id[l], y = id[r];
  int z = lca(x, y);
  if (typ[z] & 1)
    l = L[go(x, dep[x] - dep[z] - 1)], r = R[go(y, dep[y] - dep[z] - 1)];
  // 合點這裏特判的原因是因為這個合點不一定是最小的包含l，r的連續段.
  // 因為合點所代表的區間的子區間也都是連續段，而我們只需要其中的一段就夠了。
  else
    l = L[z], r = R[z];
  printf("%d %d\n", l, r);
}  // 分 lca 為析或和，這裏把葉子看成析的

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  D.build();
  build();
  dfs(rt);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    query(x, y);
  }
  return 0;
}

// 20190612
// 析合樹

參考文獻與鏈接

大米餅的博客 -【學習筆記】析合樹

  1. 劉承奧。簡單的連續段數據結構。WC2019 營員交流。 ↩

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