可持久化数据结构

• 可持久化线段树 1

历史版本修改和查询，每一次操作生成一个历史版本。

知道可持久化思想就不难了。
大概就是对于每一个点可以丢到线段树上的叶子节点。
然后对于每一个历史版本，确定了根和每一个节点的左右节点那就知道了整棵树。
所以可以直接拿一个 root 数组来作为历史版本的信息存储。
然后显而易见地，发现对于每一个修改操作都会修改不超过 $\log n$ 个点。
形式化地，就是修改了当前节点到根节点路径上的所有节点。
所有信息都可以合并一下，然后更新 root 节点。

大概就没了，时间复杂度和空间复杂度均为 $N \log N$（猜的

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int MAXN = 2e7 + 10;

struct seg { int l, r, val; } t[MAXN];
int n, Q, tot, a[N], rt[N];
int basic, opt, pos, val;

inline int New(int x) { t[++tot] = t[x]; return tot; }
inline int build(int x, int l, int r) {
  x = ++tot;
  if (l==r) { t[x].val = a[l]; return tot; }
  int mid = (l+r) >> 1;
  t[x].l = build(t[x].l, l, mid);
  t[x].r = build(t[x].r, mid+1, r);
  return x;
}

inline int upd(int x, int l, int r, int pos, int v) {
  x = New(x);
  if (l==r) { t[x].val = v; return x; }
  int mid = (l+r) >> 1;
  if (pos<=mid) t[x].l = upd(t[x].l, l, mid, pos, v);
  else t[x].r = upd(t[x].r, mid+1, r, pos, v);
  return x;
}

inline int query(int x, int l, int r, int pos) {
  if (l==r) return t[x].val;
  int mid = (l+r) >> 1;
  if (pos<=mid) return query(t[x].l, l, mid, pos);
  return query(t[x].r, mid+1, r, pos);
}

inline void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void print(int x) {
  if (x<0) { putchar('-'); x = -x; }
  if (x>9) print(x/10);
  putchar(x%10^48); return ;
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i) read(a[i]);
  rt[0] = build(0, 1, n);
  for (int i=1; i<=Q; ++i) {
    read(basic), read(opt), read(pos);
    if (opt==1) read(val), rt[i] = upd(rt[basic], 1, n, pos, val);
    else print(query(rt[basic], 1, n, pos)), puts(""), rt[i] = rt[basic];
  } return 0;
}

• 可持久化线段树 2

主席树入门题（？
这主席树还是静态的，那么我们可以乱搞了。
首先分块老哥靠边（

如果我们要找到区间第 $k$ 小那么是不是可以直接维护区间内某些值的个数
如果一段前缀某些数的个数和 $<k$ 那么可以直接遍历另外一半
所以直接想到了线段树的左儿子和右儿子 然后直接遍历搞

因为你这样显然是要建一个值域的是吧
然后因为值域你开不下啊，所以离散化一样，不改变相对关系
最后在询问值得时候代回去就可以了

重点是我们怎么维护前缀某些数个数和
你现在有一堆结构体 tree[N]
然后 $\forall \space 1 \le i \le n$，tree[i] 代表了一段前缀的信息

信息的具体处理方式可以参考这样：3 3 4 6 9 1 1 4 1

然后你离散化每一个位置维护的值就应该是其出现的次数
那么就变成这样了 3[1] 2[3] 2[4] 1[6] 1[9]
但是你每个前缀都建一颗线段树，时间复杂度抛开不说，你空间跑不了啊
然后发现每一个前缀都和前面处理的信息有极大的重复
所以参考上面的方法 直接共用一大堆节点，新建相当于 $\log N$ 了。

所以时间复杂度和空间复杂度都是 $N \log N$ 了。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, Q, tot, a[N], b[N], tmp[N];
struct seg { int l, r, val; } t[N*20];

inline void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

inline int build(int l, int r) {
  int rt = ++tot; t[rt].val = 0;
  if (l<r) {
    int mid = (l+r) >> 1;
    t[rt].l = build(l, mid);
    t[rt].r = build(mid+1, r);
  } return rt;
}

inline int upd(int pre, int l, int r, int pos) {
  int rt = ++tot;
  t[rt].l = t[pre].l, t[rt].r = t[pre].r;
  t[rt].val = t[pre].val + 1;
  if (l<r) {
    int mid = (l+r) >> 1;
    if (pos<=mid) t[rt].l = upd(t[pre].l, l, mid, pos);
    else t[rt].r = upd(t[pre].r, mid+1, r, pos);
  } return rt;
}

inline int query(int x, int y, int l, int r, int rk) {
  if (l>=r) return l;
  int val = t[t[y].l].val - t[t[x].l].val;
  int mid = (l+r) >> 1;
  if (val>=rk) return query(t[x].l, t[y].l, l, mid, rk);
  else return query(t[x].r, t[y].r, mid+1, r, rk-val);
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i)
    read(a[i]), b[i] = a[i];
  sort(b+1, b+1+n);
  int Len = unique(b+1, b+1+n)-b-1;
  tmp[0] = build(1, Len);
  for (int i=1; i<=n; ++i) {
    int cur = lower_bound(b+1, b+1+Len, a[i])-b;
    tmp[i] = upd(tmp[i-1], 1, Len, cur);
  }
  while (Q--) {
    int l, r, k; read(l), read(r), read(k);
    int id = query(tmp[l-1], tmp[r], 1, Len, k);
    printf("%d\n", b[id]);
  } return 0;
}

tmp 维护的就是上述的根，然后常规处理。

---

好的，这些就是暂时的可持久化博客了。
Flag：树套树，懒标记专题，线性基，如果咕了 QQ 催我。