可持久化 0/1 Trie

可持久化可以维护数据结构的历史版本。

对于一个字典树, 如果更改一个元素, 暴力做法是复制一个树, 让后在树上修改。其实, 这样是有很多个一定一样的点是浪费的, 真正被修改的是 \(\log_2n\) 个点, \(2\log_2n\) 条边。

优点 : 大大减低时间复杂度，还支持在线做。

缺点 : 不能传懒标记, 不知道懒标记是修改哪个版本留下的

可持久化0/1 Trie, 例题 : P3835

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, IP = 1e9;

struct TRIE{
  int cnt, son[2];
  void clear(){
    cnt = son[0] = son[1] = 0;
  }
}trie[N * 62];

int tot, ans, x, p, n, v, op, c, root[N], rak;

int push_back(){
  trie[++tot].clear();
  return tot;
}

void Insert(int p, int q, int x){
  for(int i = 30; ~i; i--){
    for(int j = 0; j <= 1; ++j){
      if(!trie[q].son[j]){
        trie[q].son[j] = push_back();
      }
    }
    c = bool((1 << i) & x);
    trie[p].son[c] = push_back();
    trie[p].son[!c] = trie[q].son[!c];
    p = trie[p].son[c], q = trie[q].son[c];
    trie[p].cnt = trie[q].cnt + 1;
  }
}

void Erase(int p, int q, int x){
  for(int i = 30; ~i; i--){
    for(int j = 0; j <= 1; ++j){
      if(!trie[q].son[j]){
        trie[q].son[j] = push_back();
      }
    }
    c = bool((1 << i) & x);
    trie[p].son[c] = push_back();
    trie[p].son[!c] = trie[q].son[!c];
    p = trie[p].son[c], q = trie[q].son[c];
    trie[p].cnt = trie[q].cnt - 1;
  }
}

int S3(int p, int x){
  ans = 0;
  for(int i = 30; ~i; i--){
    c = bool((1 << i) & x);
    if(c){
      ans += trie[trie[p].son[0]].cnt;
    }
    p = trie[p].son[c];
  }
  return ans + 1;
}

int S4(int p, int x){
  ans = 0;
  for(int i = 30; ~i; i--){
    if(trie[trie[p].son[0]].cnt >= x){
      p = trie[p].son[0];
    }
    else{
      x -= trie[trie[p].son[0]].cnt;
      p = trie[p].son[1];
      ans |= (1 << i);
    }
  }
  return ans;
}

int query(int p, int q, int x){
  for(int i = 30; ~i; i--){
    c = bool((1 << i) & x);
    p = trie[p].son[c], q = trie[q].son[c];
  }
  return trie[q].cnt - trie[p].cnt;
}

int main(){
  cin >> n;
  root[0] = push_back();
  for(int i = 1; i <= n; i++){
    cin >> v >> op >> x;
    if(op <= 2){
      root[i] = push_back();
    }
    else{
      root[i] = root[v];
    }
    if(op == 1){
      Insert(root[i], root[v], x + IP);
    }
    if(op == 2){
      if(query(root[i], root[v], x + IP)){
        Erase(root[i], root[v], x + IP);
      }
      else{
        root[i] = root[v];
      }
    }
    if(op == 3){
      cout << S3(root[i], x + IP) << '\n';
    }
    if(op == 4){
      cout << S4(root[i], x) - IP << '\n';
    }
    if(op == 5){
      rak = S3(root[i], x + IP) - 1;
      cout << S4(root[i], rak) - IP << '\n';
    }
    if(op == 6){
      rak = S3(root[i], x + IP + 1);
      cout << S4(root[i], rak) - IP << '\n';
    }
  }
  return 0;
}

可持久化线段树, 例题 : P3834

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

struct Node{
  int l, r, lson, rson, data;
}t[25 * N];

int tot, n, m, root[N], a[N], b[N], l, r, k;

int push_back(){
  t[++tot] = {0, 0, 0, 0, 0};
  return tot;
}

void renew(int p){
  t[p].data = t[t[p].lson].data + t[t[p].rson].data;
}

void build(int p, int l, int r){
  t[p].l = l, t[p].r = r;
  if(l == r){
    return;
  }
  int mid = (l + r) >> 1;
  t[p].lson = push_back(), t[p].rson = push_back();
  build(t[p].lson, l, mid);
  build(t[p].rson, mid + 1, r);
  renew(p);
}

void updata(int p1, int p2, int ok){
  t[p2] = t[p1];
  if(t[p2].l == t[p2].r){
    t[p2].data++;
    return;
  }
  int mid = (t[p1].l + t[p1].r) >> 1;
  if(ok <= mid){
    t[p2].lson = push_back();
    updata(t[p1].lson, t[p2].lson, ok);
  }
  else{
    t[p2].rson = push_back();
    updata(t[p1].rson, t[p2].rson, ok);
  }
  renew(p2);
}

int query(int p1, int p2, int ok){
  if(t[p2].l == t[p2].r){
    return t[p2].l;
  }
  int mid = (t[p2].l + t[p2].r) >> 1;
  if(t[t[p2].lson].data - t[t[p1].lson].data >= ok){
    return query(t[p1].lson, t[p2].lson, ok);
  }
  return query(t[p1].rson, t[p2].rson, ok - (t[t[p2].lson].data - t[t[p1].lson].data));
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  root[0] = push_back();
  build(1, 1, n);
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  for(int i = 1; i <= n; ++i){
    a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    root[i] = push_back();
    updata(root[i - 1], root[i], a[i]);
  }
  for(int i = 1; i <= m; ++i){
    cin >> l >> r >> k;
    cout << b[query(root[l - 1], root[r], k)] << '\n';
  }
  return 0;
}