# [模板] 可持久化线段树 & 主席树

## 实现

inline void update(int &root, int oldroot, int left, int right, itn qleft, int qright, ...){

root = ++tot;

lson[root] = lson[oldroot];
rson[root] = rson[oldroot];

... //其他数值的复制、修改等

if(left == right){
... //修改操作等
return;
}

int mid = (left + right) >> 1;

if(qleft <= mid)
update(lson[root], lson[oldroot], left, mid, num);

if(mid < qright)
update(rson[root], rson[oldroot], mid+1, right, num);

... //回溯操作等
}


## 例题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = (200000 + 10) << 5;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int sum[MAXN], lson[MAXN], rson[MAXN], tot;
int root[MAXN];

inline void build(int &root, int left, int right){
root = ++tot;

if(left == right)
return;

int mid = (left + right) >> 1;

if(left <= mid)
build(lson[root], left, mid);

if(mid < right)
build(rson[root], mid+1, right);
}

inline void update(int &root, int oldroot, int left, int right, int num){
root = ++tot;

sum[root] = sum[oldroot] + 1;
lson[root] = lson[oldroot];
rson[root] = rson[oldroot];

if(left == right){
return;
}

int mid = (left + right) >> 1;

if(num <= mid)
update(lson[root], lson[oldroot], left, mid, num);

if(mid < num)
update(rson[root], rson[oldroot], mid+1, right, num);
}

inline int query(int leftroot, int rightroot, int left, int right, int num){
int mid = (left + right) >> 1;

if(left == right)
return left;

if(num <= sum[lson[rightroot]] - sum[lson[leftroot]]){
return query(lson[leftroot], lson[rightroot], left, mid, num);
}else{
num -= sum[lson[rightroot]] - sum[lson[leftroot]];
return query(rson[leftroot], rson[rightroot], mid+1, right, num);
}
}

int num[MAXN];
int que[MAXN];
int n, m;

int main(){

for(register int i=1; i<=n; i++)

sort(que+1, que+n+1);
int cnt = unique(que+1, que+n+1) - que;

for(register int i=1; i<=n; i++){
num[i] = lower_bound(que+1, que+cnt, num[i]) - que;
}

build(root[0], 1, n);

for(register int i=1; i<=n; i++)
update(root[i], root[i-1], 1, n, num[i]);

for(register int i=1; i<=m; i++){