Persistent Balanced Tree

Persistent FHQ Treap

Prerequisite knowledge

The persistent balanced tree commonly used in OI is generally a persistent FHQ Treap, so it is recommended to learn FHQ Treap first.

Idea / approach

For a rotation-free Treap, persistence can be achieved by copying the nodes encountered on the path during Merge and Split (usually copying during Split so that earlier versions are not affected).

For a rotational Treap, in addition to copying the nodes encountered on the path, we must also copy nodes affected by rotations. If such a node has already been copied during the operation, it need not be copied again. A single rotation generally affects only two nodes, so this does not increase the time complexity.

The method above is generally called path copying.

“All supported operations can be implemented through Merge Split Newnode Build.” The Build operation is used only to construct the tree and need not concern us here; Newnode (creating a new node) is the tool used for persistence.

Observe Merge and Split: both are top-down operations!

Therefore, we can make the Treap persistent by referring to persistent operations on a segment tree.

Persistent operations

Persistence is an operation on a data structure that retains historical information, so that an earlier historical version can be used later.

For a persistent segment tree, creating each new historical version means copying the modification path along the way.

For a persistent Treap (the version commonly used in domestic OI), this means:

After copying a node $X_{a}$ (the $X$ node's $a$-th version) into its new version $X_{a+1}$ (the $X$ node's $a+1$-th version):

• If a child node $Y$ does not need its information modified, let the pointer in $X_{a+1}$ point directly to $Y_{a}$ (the $Y$ node's $a$-th version).
• Otherwise, if $Y$ needs modification, when recursing to the lower layer, create a new node $Y_{a+1}$ (the $Y$ node's $a+1$-th version) to store the new information, and let the pointer in $X_{a+1}$ point to $Y_{a+1}$ (the $Y$ node's $a+1$-th version).

Persistence

The required components are:

• A struct array storing the information of each node (usually called the tree array); (those implementing a pointer-based balanced tree may of course consider omitting this array.)

• A root-node array storing the root of each version; when querying a version, start from the node stored in the root array.

• split(), which splits two trees out of a tree.

• merge(), which merges two trees according to their random priorities.

• newNode(), which creates a node.

• build(), which builds the tree.

Split

For the split operation, create a new node along each split path to point to the split-off paths, and use std::pair to store the roots of the two newly split trees.

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

For the tree rooted at $_x$, place its first $k$ elements in one tree, and put the remaining nodes in the other tree. Return the roots of the two trees (first is the root of the first tree and second is the root of the second).

• If the left subtree of $x$ has $key \geq k$, recurse directly into the left subtree, then merge the second tree split from the left subtree with the right subtree of the current $x$.
• Otherwise recurse into the right subtree.

static std::pair<int, int> _split(int _x, int k) {
  if (_x == 0)
    return std::make_pair(0, 0);
  else {
    int _vs = ++_cnt;  // 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.

It is also implemented recursively. If the random priority of x is greater than the random priority of y, perform merge(x_{rc},y); otherwise perform merge(x,y_{lc}).

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

Prerequisite knowledge

Persistent WBLT is derived by modifying WBLT, so first learn WBLT.

Idea / approach

Use path copying to copy the nodes modified during an operation so that earlier nodes are not affected.

Handling lazy tags

To handle lazy tags, consider a persistent WBLT. A node may have multiple parents, but it can have only $0$ or $2$ children. The pushdown operation for propagating a lazy tag affects only the children. Applying pushdown to a node itself is harmless; the problem is that a child may have more than one parent. Propagating the tag to the child could add a lazy tag that does not belong to another parent's version, which is incorrect, unless the child has only that one parent. Therefore, during pushdown, copy each child and apply the lazy tag to the new child.

Implementing path copying

When performing path copying, define a refresh function that takes a node $p$ by reference, copies node $p$, creates a new node, and assigns it back to $p$. The rule for refresh is: if the node is about to be modified, or one of its children is about to change (not merely have its information modified), refresh the node; otherwise it is unnecessary.

For a static query, no refresh is needed except for pushdown. If every operation uses path copying, the order of pushdown and refresh does not matter.

A small optimization for persistent WBLT

Here is an optimization. Pushdown copies two nodes, and tags can be made persistent, but as noted above, copying is unnecessary if a child has only one parent. We can use this property to reduce redundant copies.

Record the number of parents of each node (regard the root of every version as having one parent), denoted by $use$. During every refresh, if $use\leq 1$, do not copy the node; otherwise create a new node and decrement $use$ by $1$, meaning that the parent has taken this child away. The parent can then modify the new node freely without affecting other versions. Also, whenever a node is copied, if it has children, increment each child's $use$ by $1$; when merging two subtrees, the returned node contributes one parent to each child's $use$; when deleting a node, decrement the parent count of both children. This can improve both time and space usage.

Implementation

#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 problem

This is the persistent version of the ordinary balanced tree problem, with similar operations.

The only difference is that persistent merge and split operations are used.

Recommended practice problems

1. “Luogu P3919” Persistent array (template problem)

2. “Codeforces 702F” T-shirt

3. “Luogu P5055” Persistent artistic balanced tree

4. “Luogu P5350” Sequence