Skip to content

Persistent Balanced Tree

Persistent Treap without Rotation

Prerequisites

Persistent balanced trees commonly used in OI generally refer to persistent treaps without rotation, so it is recommended to first learn Treap without rotation.

Idea/Approach

For a non-rotating treap, persistence can be achieved by copying nodes along the path during Merge and Split operations (typically copying during Split to ensure previous versions are unaffected).

For a rotating treap, in addition to copying nodes along the path, nodes affected by rotations must also be copied (if they have already been copied in this operation, no further copying is needed). A single rotation usually affects only two nodes, so this does not increase the time complexity.

The above method is generally referred to as path copying.

"All supported operations can be accomplished through Merge, Split, Newnode, Build", where Build is only used for construction and can be ignored, and Newnode (creating a new node) is the tool used for persistence.

Observing Merge and Split, we find they are both top-down operations!

Therefore, we can fully refer to the persistence operations of segment trees to make it persistent.

Persistent Operations

Persistence is an operation on a data structure that retains historical information, allowing access to previous historical versions later.

For persistent segment trees, creating a new historical version involves copying the modified path along the way.

For persistent treaps (the version commonly used in OI in China):

After copying a new version \(X_{a+1}\) (the \((a+1)\)-th version of node \(X\)) from node \(X_{a}\) (the \(a\)-th version of node \(X\)):

  • If a child node \(Y\) does not need modification, then directly point \(X_{a+1}\)'s pointer to \(Y_{a}\) (the \(a\)-th version of node \(Y\)).
  • Conversely, if \(Y\) needs modification, then recursively create a new node \(Y_{a+1}\) (the \((a+1)\)-th version of node \(Y\)) at the lower level to store the new information, and point \(X_{a+1}\)'s pointer to \(Y_{a+1}\) (the \((a+1)\)-th version of node \(Y\)).

Persistence

What is needed:

  • A struct array to store information for each node (usually called the tree array); (Of course, those who write pointer-based balanced trees may not need this array.)

  • A root node array to store the tree root of each version; each time version information is queried, start from the node stored in the root array.

  • split() splits two trees from one tree.

  • merge() merges two trees according to random weights.

  • newNode() creates a new node.

  • build() builds the tree.

Split

For the split operation, each time the path is split, create a new node pointing to the split path, and use std::pair to store the roots of the two newly split trees.

split(x,k) returns a std::pair;

It means placing the first \(k\) elements of the tree rooted at \(_x\) in one tree, and the remaining nodes in another tree, returning the roots of these two trees (first is the root of the first tree, second is the root of the second tree).

  • If the \(key\) of \(x\)'s left subtree is \(\geq k\), then directly recurse into the left subtree, and merge the second tree split from the left subtree with the current \(x\)'s right subtree.
  • Otherwise, recurse into the right subtree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
static std::pair<int, int> _split(int _x, int k) {
  if (_x == 0)
    return std::make_pair(0, 0);
  else {
    int _vs = ++_cnt;  // Create a new node (the essence of persistence)
    _trp[_vs] = _trp[_x];
    std::pair<int, int> _y;
    if (_trp[_vs].key <= k) {
      _y = _split(_trp[_vs].leaf[1], k);
      _trp[_vs].leaf[1] = _y.first;
      _y.first = _vs;
    } else {
      _y = _split(_trp[_vs].leaf[0], k);
      _trp[_vs].leaf[0] = _y.second;
      _y.second = _vs;
    }
    _trp[_vs]._update();
    return _y;
  }
}

Merge

merge(x,y) returns the root of the merged tree.

Also implemented recursively. If the random weight of x > the random weight of y, then merge(x_{rc},y), otherwise merge(x,y_{lc}).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
static int _merge(int _x, int _y) {
  if (_x == 0 || _y == 0)
    return _x ^ _y;
  else {
    if (_trp[_x].fix < _trp[_y].fix) {
      _trp[_x].leaf[1] = _merge(_trp[_x].leaf[1], _y);
      _trp[_x]._update();
      return _x;
    } else {
      _trp[_y].leaf[0] = _merge(_x, _trp[_y].leaf[0]);
      _trp[_y]._update();
      return _y;
    }
  }
}

Persistent WBLT

Prerequisites

Persistent WBLT is derived from WBLT, so first learn WBLT.

Idea/Approach

Use the path copying method to copy nodes modified during an operation, without affecting previous nodes.

Handling Lazy Tags

To handle lazy tags, consider this: in a persistent WBLT, a node may have multiple parents, but the number of children can only be \(0\) or \(2\). The pushdown operation for lazy tags only affects its children. Performing pushdown on a node has no impact; however, its children may have more than one parent. Pushing the tag down to its children may cause an extra lazy tag that does not belong to another parent's version, which is incorrect; unless the child has only one parent. Therefore, during pushdown, we should copy the child and apply the lazy tag to the new child.

Implementing Path Copying

During path copying, we can define a refresh function that takes a reference to a node \(p\), meaning copy node \(p\) to produce a new node and reassign it to \(p\). The principle of using the refresh function is: if it is about to be modified, or if its children are about to change (rather than the children's information being modified), then refresh it; otherwise, it is not necessary.

For static queries, except for pushdown, no refresh is needed. If path copying is guaranteed for all operations, the order of pushdown and refresh does not matter.

Optimization for Persistent WBLT

There is an optimization here. Observing that pushdown requires copying two nodes, one could write permanent marking, but as mentioned earlier, if a child has only one parent, copying is unnecessary. Based on this property, optimizations can be made to reduce unnecessary node copying.

Consider recording how many parents each node has (considering each version's root has one parent), denoted as \(use\). Each time refresh is called, if \(use \leq 1\), there is no need to copy the node again; otherwise, create a new node, and decrement \(use\) by \(1\), indicating the parent has taken this child away, so the parent can freely modify the new node without affecting other versions. Additionally, each time a node is copied, if the node has children, increment the \(use\) of both children by \(1\); when merging two subtrees, the returned node also has a parent \(use\) for both children; when deleting a node, both child nodes lose one parent: this can optimize some time and space.

Code Implementation

Complete Code (Persistent Artistic Balanced Tree) 
  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
212
213
214
215
216
217
218
#include <cstring>
#include <iostream>
#include <utility>
using namespace std;
using LL = long long;

template <int N>
struct WBLT {
  static constexpr double alpha = 0.292;
  int ch[N << 1][2], siz[N << 1], tot, root, tsh[N << 1], tct;
  int val[N << 1];
  LL sum[N << 1];
  bool rev[N << 1];
  int use[N << 1];

  WBLT() { root = newnode(-(int)((1u << 31) - 1)); }

  bool isleaf(int p) { return !ch[p][0]; }

  void destroy(int p) { tsh[++tct] = p; }

  void clone(int p, int q) {
    memcpy(ch[p], ch[q], sizeof ch[0]);
    val[p] = val[q];
    siz[p] = siz[q];
    sum[p] = sum[q];
    rev[p] = rev[q];
    if (!isleaf(p)) {
      use[ch[p][0]] += 1;
      use[ch[p][1]] += 1;
    }
  }

  int newnode(LL v) {
    int p = tct ? tsh[tct--] : ++tot;
    memset(ch[p], 0, sizeof ch[p]);
    val[p] = v;
    siz[p] = 1;
    sum[p] = v;
    rev[p] = false;
    use[p] = 1;
    return p;
  }

  void refresh(int &p) {
    if (use[p] <= 1) return;
    use[p] -= 1;
    int q = exchange(p, newnode(0));
    clone(p, q);
  }

  void maintain(int p) {  // also known as: pushup
    if (isleaf(p)) return;
    val[p] = val[ch[p][1]];
    sum[p] = sum[ch[p][0]] + sum[ch[p][1]];
    siz[p] = siz[ch[p][0]] + siz[ch[p][1]];
  }

  void spread(int &p) {
    if (isleaf(p)) return;
    refresh(p);
    rev[p] ^= 1;
  }

  void pushdown(int p) {
    if (!rev[p] || isleaf(p)) return;
    spread(ch[p][0]), spread(ch[p][1]);
    swap(ch[p][0], ch[p][1]);
    rev[p] = false;
  }

  void rotate(int p, int r) {
    if (isleaf(p) || isleaf(ch[p][r])) return;
    refresh(ch[p][r]);
    pushdown(ch[p][r]);
    int q = ch[p][r];
    swap(ch[p][0], ch[p][1]);
    swap(ch[p][r], ch[q][r]);
    swap(ch[q][0], ch[q][1]);
    maintain(q);
    maintain(p);
  }

  void update(int p) {  // also known as: maintain
    if (isleaf(p)) return;
    int r = siz[ch[p][0]] < siz[ch[p][1]];
    if (siz[ch[p][!r]] >= siz[p] * alpha) return;
    refresh(ch[p][r]);
    pushdown(ch[p][r]);
    if (siz[ch[ch[p][r]][!r]] >= siz[ch[p][r]] * (1 - alpha * 2) / (1 - alpha))
      rotate(ch[p][r], !r);
    rotate(p, r);
  }

  void insert(int &p, int v, int k) {
    refresh(p);
    pushdown(p);
    int r = siz[ch[p][0]] < k;
    if (isleaf(p)) {
      ch[p][0] = newnode(val[p]);
      ch[p][1] = newnode(v);
    } else {
      if (r) k -= siz[ch[p][0]];
      insert(ch[p][r], v, k);
    }
    maintain(p);
    update(p);
  }

  void erase(int &p, int k) {
    refresh(p);
    pushdown(p);
    int r = siz[ch[p][0]] < k;
    if (isleaf(ch[p][r])) {
      use[ch[p][0]] -= 1;
      use[ch[p][1]] -= 1;
      clone(p, ch[p][!r]);
    } else {
      if (r) k -= siz[ch[p][0]];
      erase(ch[p][r], k);
    }
    maintain(p);
    update(p);
  }

  int merge(int p, int q) {
    if (!p || !q) return p + q;
    if (min(siz[p], siz[q]) >= alpha * (siz[p] + siz[q])) {
      int t = newnode(0);
      ch[t][0] = p, use[p] += 1;
      ch[t][1] = q, use[q] += 1;
      maintain(t);
      return t;
    }
    if (siz[p] >= siz[q]) {
      pushdown(p);
      if (siz[ch[p][0]] >= alpha * (siz[p] + siz[q])) {
        return merge(ch[p][0], merge(ch[p][1], q));
      } else {
        pushdown(ch[p][1]);
        return merge(merge(ch[p][0], ch[ch[p][1]][0]),
                     merge(ch[ch[p][1]][1], q));
      }
    } else {
      pushdown(q);
      if (siz[ch[q][1]] >= alpha * (siz[p] + siz[q])) {
        return merge(merge(p, ch[q][0]), ch[q][1]);
      } else {
        pushdown(ch[q][0]);
        return merge(merge(p, ch[ch[q][0]][0]),
                     merge(ch[ch[q][0]][1], ch[q][1]));
      }
    }
  }

  void split(int p, int k, int &x, int &y) {
    if (!k) return x = 0, y = p, void();
    if (isleaf(p)) return x = p, y = 0, void();
    pushdown(p);
    if (k <= siz[ch[p][0]]) {
      split(ch[p][0], k, x, y);
      y = merge(y, ch[p][1]);
    } else {
      split(ch[p][1], k - siz[ch[p][0]], x, y);
      x = merge(ch[p][0], x);
    }
  }

  LL getsum(int L, int R, int &p, int l, int r) {
    if (L <= l && r <= R) return sum[p];
    pushdown(p);
    int mid = l + siz[ch[p][0]] - 1;
    LL ret = 0;
    if (L <= mid) ret += getsum(L, R, ch[p][0], l, mid);
    if (mid < R) ret += getsum(L, R, ch[p][1], mid + 1, r);
    return ret;
  }

  LL getsum(int &p, int L, int R) { return getsum(L + 1, R + 1, p, 1, siz[p]); }
};

WBLT<6400010> t;
int m;
int root[500010];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> m;
  root[0] = t.root;
  LL lastans = 0;
  for (int i = 1; i <= m; i++) {
    LL op, l, r;
    int v;
    cin >> v >> op >> l;
    t.use[root[i] = root[v]] += 1;
    if (op != 2) cin >> r;
    l ^= lastans, r ^= lastans;
    int x, y, z;
    switch (op) {
      case 1:
        t.insert(root[i], r, l + 1);
        break;
      case 2:
        t.erase(root[i], l + 1);
        break;
      case 3:
        t.split(root[i], l, x, y);
        t.split(y, r - l + 1, y, z);
        t.spread(y);
        root[i] = t.merge(x, t.merge(y, z));
        break;
      case 4:
        cout << (lastans = t.getsum(root[i], l, r)) << endl;
        break;
    }
  }
  return 0;
}

Example Problems

Luogu P3835【Template】Persistent Balanced Tree

You need to implement a data structure that supports the following operations (initially the data structure contains no data):

  1. Insert number \(x\);
  2. Delete number \(x\) (if there are multiple identical numbers, delete only one; if none exist, ignore this operation);
  3. Query the rank of number \(x\) (rank defined as the number of numbers smaller than the current number + 1);
  4. Query the number with rank \(x\);
  5. Find the predecessor of \(x\) (predecessor defined as the largest number less than \(x\), output \(-2\,147\,483\,647\) if it does not exist);
  6. Find the successor of \(x\) (successor defined as the smallest number greater than \(x\), output \(2\,147\,483\,647\) if it does not exist).

All the above operations are based on a certain historical version, while generating a new version (operations 3, 4, 5, 6 keep the original version unchanged). The version number is the sequence number of the operation. Specifically, the initial version number is 0.

This is the persistent version of the Ordinary Balanced Tree problem, with operations similar to that problem.

It only uses persistent merge and split operations.

  1. 「Luogu P3919」Persistent Array (Template Problem)

  2. 「Codeforces 702F」T-shirt

  3. 「Luogu P5055」Persistent Artistic Balanced Tree

  4. 「Luogu P5350」Sequence

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