可持久化（线段树(主席树)，tire）
介绍
可持久化数据结构是一种能够在多次修改操作后仍能访问历史版本数据的数据结构。以下是对它的详细介绍：
定义与特点
定义：可持久化数据结构通过某种方式记录数据结构在不同时间点的状态，使得在进行一系列插入、删除或修改操作后，仍然可以高效地访问和查询过去某个时刻的数据结构状态。
特点：它允许在不复制整个数据结构的情况下，创建多个版本的数据结构，每个版本都反映了在某个特定操作序列之后的数据状态，从而节省了大量的空间和时间开销。
常见类型
可持久化数组：可以在数组的基础上，通过记录每次修改的位置和值，实现对数组历史版本的访问。例如，通过使用写时复制技术，当修改数组的某个元素时，只复制需要修改的部分，而不是整个数组，从而创建一个新的版本。
可持久化线段树：在普通线段树的基础上进行扩展，支持对线段树的历史版本进行查询。它通过记录每个节点的修改历史，使得在查询时可以根据不同的版本号来访问相应版本的线段树信息。常用于区间查询、修改等问题，例如在动态维护区间最大值、最小值、区间和等场景中广泛应用。
可持久化 Trie 树：能够保存 Trie 树在不同插入或删除操作后的状态。通过在 Trie 树的节点中记录版本信息或使用额外的数据结构来跟踪节点的变化，实现对历史版本的回溯和查询。在处理字符串相关问题，如字符串的插入、删除和查找历史记录等方面有重要应用。
实现方式
写时复制：当需要修改数据结构时，不直接在原数据结构上进行修改，而是创建一个新的节点或数据结构，并将原数据结构中的相关部分复制到新的结构中，然后在新结构上进行修改。这样可以保留原数据结构的状态，同时创建一个新的版本。
路径分裂：对于一些树形数据结构，如线段树，当进行修改时，只分裂需要修改的路径上的节点，而不是整个树。通过这种方式，可以在不影响其他路径的情况下，高效地创建新的版本。
应用场景
版本控制：在软件开发中，可持久化数据结构可以用于实现版本控制系统，记录文件或代码的历史版本，方便开发人员进行回溯和比较。
数据库系统：用于实现数据库的多版本并发控制（MVCC），允许多个事务同时访问数据库的不同版本，提高并发性能和数据一致性。
算法竞赛：在解决一些需要处理历史数据或动态查询的算法问题时，可持久化数据结构可以提供高效的解决方案，例如在处理区间查询、动态规划等问题中。
题目：
最大异或和:
题目描述
给定一个非负整数序列 {a}，初始长度为 N。
有 M 个操作，有以下两种操作类型：
A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 加 1。
Q l r x：询问操作，你需要找到一个位置 p，满足 l≤p≤r，使得：a[p]⊕a[p+1]⊕...⊕a[N]⊕x 最大，输出最大值。
输入格式
第一行包含两个整数 N,M，含义如问题描述所示。
第二行包含 N 个非负整数，表示初始的序列 A。
接下来 M 行，每行描述一个操作，格式如题面所述。
输出格式
假设询问操作有 T 个，则输出应该有 T 行，每行一个整数表示询问的答案。
分析：
使用可持久化tire来存储每个版本的tire，然后通过贪心操作，从第r版的tire开始贪心的搜索，我们从最高位大向最低位搜，因为是异或和，所以总是希望搜索到和当前值不同的数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=600009;
char op[2];
int s[N];
int n,m;
int tr[28*N][3];
int max_id[N*28];
int idx=0;
int root[N*28];
void insert(int i,int k,int pre,int cur){
if(k<0){
max_id[cur]=i;
return;
}
int v=s[i]>>k&1;
if(pre)tr[cur][v^1]=tr[pre][v^1];
tr[cur][v]=++idx;
insert(i,k-1,tr[pre][v],tr[cur][v]);
max_id[cur]=max(max_id[tr[cur][0]],max_id[tr[cur][1]]);
}
int query(int l, int r, int x) {
int p = root[r];
int res = 0;
for (int i = 23; i >= 0; i--) {
int v = x >> i & 1;
if (max_id[tr[p][v ^ 1]] >= l) {
res += (1 << i);
p = tr[p][v ^ 1];
} else {
p = tr[p][v];
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
max_id[0]=-1;
int tmp;
root[0]=++idx;
insert(0,23,0,root[0]);
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
s[i]=s[i-1]^tmp;
root[i]=++idx;
insert(i,23,root[i-1],root[i]);
}
while(m--){
scanf("%s",op);
if(op[0]=='A'){
int x;
scanf("%d",&x);
n++;
root[n]=++idx;
s[n]=x^s[n-1];
insert(n,23,root[n-1],root[n]);
}else if(op[0]=='Q'){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
cout<<query(l-1,r-1,s[n]^x)<<endl;
}
}
}
第k小数
给定长度为 NN 的整数序列 AA，下标为 1∼N1∼N。
现在要执行 MM 次操作，其中第 ii 次操作为给出三个整数 li,ri,kili,ri,ki，求 A[li],A[li+1],…,A[ri]A[li],A[li+1],…,A[ri] (即 AA 的下标区间 [li,ri][li,ri])中第 kiki 小的数是多少。
输入格式
第一行包含两个整数 NN 和 MM。
第二行包含 NN 个整数，表示整数序列 AA。
接下来 MM 行，每行包含三个整数 li,ri,kili,ri,ki，用以描述第 ii 次操作。
输出格式
对于每次操作输出一个结果，表示在该次操作中，第 kk 小的数的数值。
每个结果占一行。
分析：
数据预处理
首先对原始数组进行离散化，将数值映射到紧凑的整数空间。例如原数组 [2,6,4,3,6] 离散化为 [2,3,4,6]，建立索引映射关系。这一步压缩了值域范围，使得线段树的高度与离散化后的值域大小相关，而非原始数据范围，显著降低空间和时间复杂度。
主席树构建
初始化一棵覆盖离散化值域的空树作为基准版本（root[0]）。接着按顺序处理原数组的每个元素，逐个生成新版本树。每次插入元素时，从根节点开始复制路径上的所有节点，并在目标路径的叶子节点处增加计数器。例如插入元素 3（映射为索引1），会复制旧版本的右子树路径，最终在索引1的叶子节点处将计数加1，同时更新路径上所有父节点的计数器。这种增量构建方式保证了每个版本树 root[i] 完整记录前 i 个元素的分布情况。
区间查询处理
当处理查询 [l, r, k] 时，利用两个版本树 root[r] 和 root[l-1] 的差值来获取区间 [l, r] 内的元素分布。从根节点开始递归搜索，比较左右子树的元素数量差：若左子树的元素数量足够覆盖 k，则进入左子树继续搜索；否则进入右子树，并将 k 减去左子树的元素数量。例如查询区间 [1,4] 的第3小元素时，通过计算 root[4] 与 root[0] 的差值，发现左子树（值域 [2,3]）包含2个元素，右子树（值域 [4,6]）包含2个元素，第3小需进入右子树，最终定位到离散化索引2（对应原始值4）。
关键设计细节
可持久化实现：每次插入仅复制修改路径的节点，其余节点共享历史版本，避免完全重建树结构，空间复杂度控制在 O(n log n)。
计数同步更新：插入过程中，从根节点到叶子节点的整条路径上的所有父节点均需更新计数器，确保非叶子节点能正确反映子树的总元素数。
版本链管理：显式保存每个前缀版本的根节点，形成从 root[0] 到 root[n] 的完整版本链，查询时通过版本差值快速定位区间。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m;
vector<int> rk;
int a[N];
struct node {
int l, r, cnt;
} tr[N * 20]; // 适当增大节点数防止越界
int root[N], idx = 0; // root数组大小改为N
int find(int x) {
return lower_bound(rk.begin(), rk.end(), x) - rk.begin();
}
int build(int l, int r) {
int p = ++idx;
if (l == r) {
tr[p].cnt = 0; // 显式初始化
return p;
}
int mid = (l + r) >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
tr[p].cnt = 0; // 显式初始化
return p;
}
int insert(int p, int l, int r, int x) {
int q = ++idx;
tr[q] = tr[p];
if (l == r) {
tr[q].cnt++;
return q;
}
int mid = (l + r) >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int q, int p, int l, int r, int k) {
if (l == r) return r;
int cntl = tr[tr[p].l].cnt - tr[tr[q].l].cnt;
int mid = (l + r) >> 1;
if (k <= cntl) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cntl);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
rk.push_back(a[i]);
}
// 离散化处理
sort(rk.begin(), rk.end());
rk.erase(unique(rk.begin(), rk.end()), rk.end());
// 建树
root[0] = build(0, rk.size() - 1);
for (int i = 1; i <= n; i++) {
root[i] = insert(root[i - 1], 0, rk.size() - 1, find(a[i]));
}
// 处理查询
while (m--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int pos = query(root[l - 1], root[r], 0, rk.size() - 1, k);
printf("%d\n", rk[pos]); // 使用printf更高效
}
return 0;
}