可持久化线段树

主席树

主席树全称是可持久化权值线段树，参见知乎讨论。

关于函数式线段树

函数式线段树 是指使用函数式编程思想的线段树。在函数式编程思想中，将计算机运算视为数学函数，并避免可改变的状态或变量。不难发现，函数式线段树是完全可持久化的。

引入

先引入一道题目：给定个整数构成的序列，将对于指定的闭区间查询其区间内的第小值。

你该如何解决？

一种可行的方案是：使用主席树。主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第小。

怎么保存呢？简单暴力一点，每次开一棵线段树呗。
那空间还不爆掉？

解释

我们分析一下，发现每次修改操作修改的点的个数是一样的。
（例如下图，修改了中对应权值为 1 的结点，红色的点即为更改的点）

只更改了 $O(\log{n})$ 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度。
注意主席树不能使用堆式存储法，就是说不能用 $x\times 2$ ， $x\times 2+1$ 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。
所以我们只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。

我们把问题简化一下：每次求区间内的小值。
怎么做呢？只需要找到插入 r 时的根节点版本，然后用普通权值线段树（有的叫键值线段树/值域线段树）做就行了。

这个相信大家都能理解，回到原问题——求区间小值。
这里我们再联系另外一个知识：前缀和。
这个小东西巧妙运用了区间减法的性质，通过预处理从而达到回答每个询问。

我们可以发现，主席树统计的信息也满足这个性质。
所以……如果需要得到的统计信息，只需要用的信息减去的信息就行了。

至此，该问题解决！

关于空间问题，我们分析一下：由于我们是动态开点的，所以一棵线段树只会出现个结点。
然后，有次修改，每次至多增加 $\lceil\log_2{n}\rceil+1$ 个结点。因此，最坏情况下次修改后的结点总数会达到 $2n-1+n(\lceil\log_2{n}\rceil+1)$ 。此题的 $n \leq 10^5$ ，单次修改至多增加 $\lceil\log_2{10^5}\rceil+1 = 18$ 个结点，故次修改后的结点总数为 $2\times 10^5-1+18\times 10^5$ ，忽略掉，大概就是 $20\times 10^5$ 。

最后给一个忠告：千万不要吝啬空间（大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）！大胆一点，直接上个 $2^5\times 10^5$ ，接近原空间的两倍（即 n << 5）。

实现

#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;
}

拓展：基于主席树的可持久化并查集

主席树是实现可持久化并查集的便捷方式，在此也提供一个基于主席树的可持久化并查集实现示例。

#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

本页面最近更新：2023/5/21 15:58:56，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：abc1763613206, H-J-Granger, ouuan, Alpha1022, billchenchina, ChungZH, cjsoft, countercurrent-time, EndlessCheng, Enter-tainer, Honeta, hsfzLZH1, iamtwz, Ir1d, ksyx, Marcythm, NachtgeistW, renbaoshuo, StudyingFather, SukkaW, Tiphereth-A, william-song-shy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用