Persistent Segment Tree

The full name of Persistent Segment Tree is Persistent Weight Segment Tree. See Zhihu discussion.

About Functional Segment Tree

Functional Segment Tree refers to a segment tree that uses functional programming ideas. In functional programming, computations are treated as mathematical functions, and mutable states or variables are avoided. It is not difficult to see that functional segment trees are fully persistent.

Introduction

First, let's introduce a problem: Given a sequence \(a\) of \(n\) integers, for a specified closed interval \([l, r]\), query the \(k\)-th smallest value within that interval.

How would you solve it?

One feasible solution is: use a Persistent Segment Tree. The main idea of the Persistent Segment Tree is: save the historical version after each insertion operation to facilitate querying the \(k\)-th smallest value in an interval.

How to save? Simply and brutally, create a new segment tree each time.
Wouldn't that blow up the space?

Explanation

We analyze and find that the number of nodes modified in each update operation is the same.
(For example, in the figure below, the node corresponding to weight 1 in \([1,8]\) is modified, and the red points are the changed nodes)

Only \(O(\log{n})\) nodes are changed, forming a chain, meaning the number of nodes changed each time = the height of the tree.
Note that the Persistent Segment Tree cannot use heap storage, meaning we cannot use \(x\times 2\), \(x\times 2+1\) to represent left and right children. Instead, we should dynamically allocate nodes and save the left and right child indices for each node.
So, by recording the left and right children and saving the root node when each number is inserted, we can achieve persistence.

Let's simplify the problem: each time, find the \(k\)-th smallest value in the interval \([1,r]\).
How to do it? Just find the root node version when inserting r, and then use an ordinary Weight Segment Tree (also called Key-Value Segment Tree / Value Range Segment Tree).

I believe everyone can understand this. Back to the original problem—finding the \(k\)-th smallest value in the interval \([l,r]\).
Here we relate to another concept: Prefix Sum.
This little thing cleverly uses the property of interval subtraction, achieving \(O(1)\) answers to each query through preprocessing.

We can find that the statistical information of the Persistent Segment Tree also satisfies this property.
So... if we need the statistical information of \([l,r]\), we just need to subtract the information of \([1,l - 1]\) from the information of \([1,r]\).

Thus, the problem is solved!

Regarding the space issue, let's analyze: Since we dynamically allocate nodes, a segment tree will only have \(2n-1\) nodes.
Then, there are \(n\) modifications, each adding at most \(\lceil\log_2{n}\rceil+1\) nodes. Therefore, in the worst case, the total number of nodes after \(n\) modifications will reach \(2n-1+n(\lceil\log_2{n}\rceil+1)\). For this problem, \(n \leq 10^5\), a single modification adds at most \(\lceil\log_2{10^5}\rceil+1 = 18\) nodes, so the total number of nodes after \(n\) modifications is \(2\times 10^5-1+18\times 10^5\), ignoring \(-1\), roughly \(20\times 10^5\).

Finally, a piece of advice: Never be stingy with space (in most problems, the space limit is relatively lenient, so generally there's no need to worry about exceeding the space limit)! Be bold, directly use \(2^5\times 10^5\), close to twice the original space (i.e., 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 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 node of this subtree
}

int update(int k, int l, int r, int root) {  // insertion operation
  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 operation
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // get the number of values stored in the left child through interval subtraction
  if (l == r) return l;
  if (k <= x)  // if k is less than or equal to x, then the k-th smallest number is stored in the left child
    return query(ls[u], ls[v], l, mid, k);
  else  // otherwise, it's 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 query
  }
}

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

Extension: Persistent Union-Find Based on Persistent Segment Tree

The Persistent Segment Tree is a convenient way to implement Persistent Union-Find. Here is also an example implementation of Persistent Union-Find based on Persistent Segment 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 1 modifies twice: once for parent node, once for parent's 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 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 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 parent node (value in 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 root node
  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 parent node (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)) {  // Union 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

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