Persistent Segment Tree

Chairman Tree

The full name of a chairman tree is a persistent segment tree over values; see the Zhihu discussion.

Introduction

Consider the following problem: given a sequence $a$ of $n$ integers, answer the $k$-th smallest value in a specified closed interval $[l, r]$.

How should we solve it?

One possible approach is to use a chairman tree. The main idea of a chairman tree is to preserve the historical version after every insertion, so that we can query the $k$-th smallest value in an interval.

How do we preserve the versions? The straightforward approach is to build a segment tree every time.
Wouldn't the space usage explode?

Explanation

Analyzing the problem, we find that every update modifies the same number of points.
(For example, in the figure below, the node corresponding to value 1 in $[1,8]$ is modified; the red nodes are the changed nodes.)

Only $O(\log{n})$ nodes are changed, forming a chain. In other words, the number of nodes changed each time equals the tree height.
Note that a chairman tree cannot use heap-style storage: we cannot use $x\times 2$ and $x\times 2+1$ to represent the left and right children. Instead, we should create nodes dynamically and store the indices of both children. Therefore, in addition to recording the children, we only need to save the root node corresponding to the insertion of each number to obtain persistence.

Let us simplify the problem: find the $k$-th smallest value in the interval $[1,r]$ each time. How can we do this? We only need to find the root-node version at the time r was inserted, and then use an ordinary segment tree over values (also called a key-value segment tree or value-domain segment tree).

This should be understandable. Returning to the original problem—finding the $k$-th smallest value in $[l,r]$—we connect it with another idea: prefix sums.
This small technique makes clever use of interval subtraction and answers every query in $O(1)$ time after preprocessing.

We can see that the information counted by a chairman tree also satisfies this property.
Thus, to obtain the information for $[l,r]$, we only need to subtract the information for $[1,l - 1]$ from that for $[1,r]$.

The problem is now solved!

For the space usage, because nodes are created dynamically, a single segment tree has only $2n-1$ nodes.
There are $n$ updates, and each adds at most $\lceil\log_2{n}\rceil+1$ nodes. Therefore, in the worst case, the total number of nodes after $n$ updates reaches $2n-1+n(\lceil\log_2{n}\rceil+1)$. For this problem, $n \leq 10^5$, and one update adds at most $\lceil\log_2{10^5}\rceil+1 = 18$ nodes. Thus, after $n$ updates the total is $2\times 10^5-1+18\times 10^5$ nodes; ignoring $-1$, this is approximately $20\times 10^5$.

Finally, one piece of advice: never skimp on space (most problems have relatively generous memory limits, so there is generally no need to worry about exceeding the limit)! Be bold and use $2^5\times 10^5$, close to twice the original space (that is, n << 5).

Implementation

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr int MAXN = 1e5;  // Data range
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) {  // Discretization
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r) {  // Build the tree
  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;  // Return the root of this subtree
}

int update(int k, int l, int r, int root) {  // Insertion
  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) {  // Query
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // Obtain the number of values stored in the left child by interval subtraction
  if (l == r) return l;
  if (k <= x)  // If k is no greater than x, the k-th smallest value is in the left child
    return query(ls[u], ls[v], l, mid, k);
  else  // Otherwise it is in the right child
    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)]);  // Answer the query
  }
}

int main() {
  init();
  work();
  return 0;
}

Extension: Persistent Disjoint-Set Union Based on a Chairman Tree

A chairman tree is a convenient way to implement a persistent disjoint-set union. Here is an example implementation based on a chairman tree.

#include <algorithm>
#include <iostream>
using namespace std;

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

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

SegmentTree
    t[MAXN * 2 +
      MAXM * 40];  // Each operation modifies twice: once for the parent and once for the rank
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) {  // Query the rank
  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) {  // Modify the rank (height)
  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) {  // Query the parent (the value in the sequence)
  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) {  // Query the root
  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) {  // Modify the parent (merge)
  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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  rt[0] = build(1, n);
  for (int i = 1; i <= m; i++) {
    int op, a, b;

    cin >> op;
    if (op == 1) {
      cin >> 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)) {  // Merge by rank
          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) {
      cin >> a;
      rt[i] = rt[a];
    } else {
      cin >> a >> b;
      rt[i] = rt[i - 1];
      cout << (findRoot(rt[i], a) == findRoot(rt[i], b)) << '\n';
    }
  }

  return 0;
}

References

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

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