跳转至

可持久化線段樹

主席樹

主席樹全稱是可持久化權值線段樹，參見 知乎討論。

關於函數式線段樹

函數式線段樹 是指使用函數式編程思想的線段樹。在函數式編程思想中，將計算機運算視為數學函數，並避免可改變的狀態或變量。不難發現，函數式線段樹是 完全可持久化 的。

引入

先引入一道題目：給定 \(n\) 個整數構成的序列 \(a\)，將對於指定的閉區間 \([l, r]\) 查詢其區間內的第 \(k\) 小值。

你該如何解決？

一種可行的方案是：使用主席樹。 主席樹的主要思想就是：保存每次插入操作時的歷史版本，以便查詢區間第 \(k\) 小。

怎麼保存呢？簡單暴力一點，每次開一棵線段樹唄。
那空間還不爆掉？

解釋

我們分析一下，發現每次修改操作修改的點的個數是一樣的。
（例如下圖，修改了 \([1,8]\) 中對應權值為 1 的結點，紅色的點即為更改的點）

只更改了 \(O(\log{n})\) 個結點，形成一條鏈，也就是説每次更改的結點數 = 樹的高度。
注意主席樹不能使用堆式存儲法，就是説不能用 \(x\times 2\)，\(x\times 2+1\) 來表示左右兒子，而是應該動態開點，並保存每個節點的左右兒子編號。
所以我們只要在記錄左右兒子的基礎上，保存插入每個數的時候的根節點就可以實現持久化了。

我們把問題簡化一下：每次求 \([1,r]\) 區間內的 \(k\) 小值。
怎麼做呢？只需要找到插入 r 時的根節點版本，然後用普通權值線段樹（有的叫鍵值線段樹/值域線段樹）做就行了。

這個相信大家都能理解，回到原問題——求 \([l,r]\) 區間 \(k\) 小值。
這裏我們再聯繫另外一個知識：前綴和。
這個小東西巧妙運用了區間減法的性質，通過預處理從而達到 \(O(1)\) 回答每個詢問。

我們可以發現，主席樹統計的信息也滿足這個性質。
所以……如果需要得到 \([l,r]\) 的統計信息，只需要用 \([1,r]\) 的信息減去 \([1,l - 1]\) 的信息就行了。

至此，該問題解決！

關於空間問題，我們分析一下：由於我們是動態開點的，所以一棵線段樹只會出現 \(2n-1\) 個結點。
然後，有 \(n\) 次修改，每次至多增加 \(\lceil\log_2{n}\rceil+1\) 個結點。因此，最壞情況下 \(n\) 次修改後的結點總數會達到 \(2n-1+n(\lceil\log_2{n}\rceil+1)\)。 此題的 \(n \leq 10^5\)，單次修改至多增加 \(\lceil\log_2{10^5}\rceil+1 = 18\) 個結點，故 \(n\) 次修改後的結點總數為 \(2\times 10^5-1+18\times 10^5\)，忽略掉 \(-1\)，大概就是 \(20\times 10^5\)。

最後給一個忠告：千萬不要吝嗇空間（大多數題目中空間限制都較為寬鬆，因此一般不用擔心空間超限的問題）！大膽一點，直接上個 \(2^5\times 10^5\)，接近原空間的兩倍（即 n << 5）。

實現

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5;  // 數據範圍
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
    rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;

int getid(const int &val) {  // 離散化
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r) {  // 建樹
  int root = ++tot;
  if (l == r) return root;
  int mid = l + r >> 1;
  ls[root] = build(l, mid);
  rs[root] = build(mid + 1, r);
  return root;  // 返回該子樹的根節點
}

int update(int k, int l, int r, int root) {  // 插入操作
  int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  int mid = l + r >> 1;
  if (k <= mid)
    ls[dir] = update(k, l, mid, ls[dir]);
  else
    rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}

int query(int u, int v, int l, int r, int k) {  // 查詢操作
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // 通過區間減法得到左兒子中所存儲的數值個數
  if (l == r) return l;
  if (k <= x)  // 若 k 小於等於 x ，則説明第 k 小的數字存儲在在左兒子中
    return query(ls[u], ls[v], l, mid, k);
  else  // 否則説明在右兒子中
    return query(rs[u], rs[v], mid + 1, r, k - x);
}

void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  memcpy(ind, a, sizeof ind);
  sort(ind + 1, ind + n + 1);
  len = unique(ind + 1, ind + n + 1) - ind - 1;
  rt[0] = build(1, len);
  for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

int l, r, k;

void work() {
  while (m--) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]);  // 回答詢問
  }
}

int main() {
  init();
  work();
  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
 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
#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
  int lc, rc, val, rnk;
};

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

SegmentTree
    t[MAXN * 2 +
      MAXM * 40];  // 每次操作1会修改两次，一次修改父节点，一次修改父节点的秩
int rt[MAXM];
int n, m, tot;

int build(int l, int r) {
  int p = ++tot;
  if (l == r) {
    t[p].val = l;
    t[p].rnk = 1;
    return p;
  }
  int mid = (l + r) / 2;
  t[p].lc = build(l, mid);
  t[p].rc = build(mid + 1, r);
  return p;
}

int getRnk(int p, int l, int r, int pos) {  // 查询秩
  if (l == r) {
    return t[p].rnk;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) {
    return getRnk(t[p].lc, l, mid, pos);
  } else {
    return getRnk(t[p].rc, mid + 1, r, pos);
  }
}

int modifyRnk(int now, int l, int r, int pos, int val) {  // 修改秩（高度）
  int p = ++tot;
  t[p] = t[now];
  if (l == r) {
    t[p].rnk = max(t[p].rnk, val);
    return p;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) {
    t[p].lc = modifyRnk(t[now].lc, l, mid, pos, val);
  } else {
    t[p].rc = modifyRnk(t[now].rc, mid + 1, r, pos, val);
  }
  return p;
}

int query(int p, int l, int r, int pos) {  // 查询父节点（序列中的值）
  if (l == r) {
    return t[p].val;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) {
    return query(t[p].lc, l, mid, pos);
  } else {
    return query(t[p].rc, mid + 1, r, pos);
  }
}

int findRoot(int p, int pos) {  // 查询根节点
  int f = query(p, 1, n, pos);
  if (pos == f) {
    return pos;
  }
  return findRoot(p, f);
}

int modify(int now, int l, int r, int pos, int fa) {  // 修改父节点（合并）
  int p = ++tot;
  t[p] = t[now];
  if (l == r) {
    t[p].val = fa;
    return p;
  }
  int mid = (l + r) / 2;
  if (pos <= mid) {
    t[p].lc = modify(t[now].lc, l, mid, pos, fa);
  } else {
    t[p].rc = modify(t[now].rc, mid + 1, r, pos, fa);
  }
  return p;
}

int main() {
  scanf("%d%d", &n, &m);
  rt[0] = build(1, n);
  for (int i = 1; i <= m; i++) {
    int op, a, b;

    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &a, &b);
      int fa = findRoot(rt[i - 1], a), fb = findRoot(rt[i - 1], b);
      if (fa != fb) {
        if (getRnk(rt[i - 1], 1, n, fa) >
            getRnk(rt[i - 1], 1, n, fb)) {  // 按秩合并
          swap(fa, fb);
        }
        int tmp = modify(rt[i - 1], 1, n, fa, fb);
        rt[i] = modifyRnk(tmp, 1, n, fb, getRnk(rt[i - 1], 1, n, fa) + 1);
      } else {
        rt[i] = rt[i - 1];
      }
    } else if (op == 2) {
      scanf("%d", &a);
      rt[i] = rt[a];
    } else {
      scanf("%d%d", &a, &b);
      rt[i] = rt[i - 1];
      if (findRoot(rt[i], a) == findRoot(rt[i], b)) {
        printf("1\n");
      } else {
        printf("0\n");
      }
    }
  }

  return 0;
}

參考

https://en.wikipedia.org/wiki/Persistent_data_structure

https://www.cnblogs.com/zinthos/p/3899565.html

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