【可持久化数据结构】主席树算法 & 可持久化线段树
前置知识：链式线段树，权值线段树思想。
简介
主席树是一种算法，不是一种数据结构，它的思想直接贯穿了诸多可持久化数据结构，典型的例子就是可持久化线段树和基于可持久化数组实现的可持久化并查集。本文将围绕可持久化线段树进行讲述。
主要思想
对于可持久化数据结构，需要维护历史信息，因此每进行一次修改，就需要申请新的空间建立起一个新的历史状态的数据结构。而主席树的思想就是，尽可能地把这一过程开支的时间、空间减小，通常情况下可以将时空复杂度降到
动态开点（单点修改）
以线段树为例，如果我们只进行单点修改，难么受到影响的就只有被修改的单点和其所有的直系父结点，这也就有了 OI-Wiki 中的一个典型的例图：
那如何实现呢？链式线段树的优势得以体现，对于每次修改，受影响的就只有左右孩子中的一个，因此只有一个孩子会动态开点，另一个孩子可以直接继承。也就是说被修改的结点相对于修改前，有改动的，仅仅只有维护的信息和指向被修改的一个孩子结点的下标。
综上可以得出，主席树算法在修改方面的复杂度就是
具有典型链式风格的代码如下：
int change(int idx , int l , int r , int q , int val){
Tree tmp = t[idx];//在原结点的基础上进行修改
if(l == r){
tmp.v += val;
t.push_back(tmp);//动态开点
return t.size() - 1;//返回开点后的下标
}
int mid = (l + r) >> 1;
if(q <= mid){//修改孩子结点和父结点指向被修改的孩子结点的下标
tmp.l = change(tmp.l , l , mid , q , val);
}else{
tmp.r = change(tmp.r , mid + 1 , r , q , val);
}
tmp.v = t[tmp.l].v + t[tmp.r].v;
t.push_back(tmp);//动态开点
return t.size() - 1;//返回开点后的下标
}我写的权值树是用动态数组储存的，因此不用考虑要开的空间大小，而且通常情况下，吸了氧的动态数组的结点拓展操作一般不会被卡。
拓展：区间修改上的动态开点
在主席树中，我们通常使用的是单点修改上的动态开点，但总有一些毒瘤出题人造一堆工业垃圾，要你维护区间修改上的动态开点，如：具有区间修改操作的历史区间求和，这就很恶心，也很无聊（让我想起了异或卷积）。
事实上，这种动态开点的方式与单点修改差不多。几乎同普通线段树的区间修改一样，只是还要对区间修改影响到维护信息的所有结点进行动态开点，但可持久化数据结构要维护的历史信息不能合并，也就是可持久化线段树不支持标记下溢，那该怎么办？一个经典的优化方案：标记永久化。
同样风格的代码如下：
int upd(int l , int r , int ql , int qr , int idx , long long val) { //修改操作
Tree tmp = tree[idx];
if(ql <= l && r <= qr) {
tmp.v += (r - l + 1) * val , tmp.lazy += val;
tree.push_back(tmp); // 动态开点
return tree.size() - 1;
}
int mid = (l + r) >> 1;
if(l <= qr && qr <= mid) { //只对包含修改区间的结点进行动态开点
tmp.l = upd(l , mid , ql , qr , tmp.l , val);
} else if(mid < ql && ql <= r) {
tmp.r = upd(mid + 1 , r , ql , qr , tmp.r , val);
} else {
tmp.l = upd(l , mid , ql , qr , tmp.l , val);
tmp.r = upd(mid + 1 , r , ql , qr , tmp.r , val);
}
tmp.v = tree[tmp.cl].v + tree[tmp.cr].v;
tree.push_back(tmp); //动态开点
return tree.size() - 1;
}
long long qry(int l , int r , int ql , int qr , int idx , int lazy) { //查询操作
Tree tmp = tree[idx];
if(qr < l || r < ql) return 0;
if(ql <= l && r <= qr) return tmp.v + (r - l + 1) * lazy;
int mid = (l + r) >> 1;
lazy += tmp.lazy; //标记永久化
return qry(l , mid , ql , qr , tmp.l , lazy) + qry(mid + 1 , r , ql , qr , tmp.r , lazy);
}即使是区间修改，动态开点的时间、空间的常数依旧是个位级的，因此不必担心常数被卡（如果被卡了，只能说明这道题是工业垃圾中的工业垃圾）。
例题一：【模板】可持久化线段树 1（可持久化数组）
本题是可持久化线段树的经典例题，建议读懂题后再看思路（这道题的题目描述很抽象）。
参考思路如下：
题目让我们维护一个长度为
参考代码如下：
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus return //奇怪的码风
#define fast() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 1e6+5;
const int inf = INT_MAX;
inline int read() { //浓缩后的快读
int x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct Tree{
int l , r , v;
};
vector<Tree>t;
int root[N];
int n,m,a[N];
int change(int idx , int l , int r , int q , int val){ //单点修改
Tree tmp = t[idx];
if(l == r){
tmp.v = val; //单点赋值
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
int mid = (l + r) >> 1;
if(q <= mid){
tmp.l = change(tmp.l , l , mid , q , val);
}else{
tmp.r = change(tmp.r , mid + 1 , r , q , val);
}
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
int query(int idx , int l , int r , int q){ //单点查询
if(l == r){
I_love_Foccarus t[idx].v;
}
int mid = (l + r) >> 1;
if(q <= mid) I_love_Foccarus query(t[idx].l , l , mid , q);
else I_love_Foccarus query(t[idx].r , mid + 1 , r , q);
}
int build(int l , int r){ //正常的链式建树
Tree tmp;
if(l == r){
tmp.l = tmp.r = -1 , tmp.v = a[l];
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
int mid = (l + r) >> 1;
tmp.l = build(l , mid) , tmp.r = build(mid + 1 , r);
tmp.v = -1;
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
signed main() {
//fast();
int n , q;
in(n) , in(q);
rep(i , 1 , n)in(a[i]);
root[0] = build(1,n);//建树得到的初始状态
rep(i , 1 , q){
int qt , op , qx , val , l , r;
in(qt) , in(op) , in(qx);
if(op == 1){
in(val);
root[i] = change(root[qt] , 1 , n , qx , val);//记录修改后新开的根结点
}else{
cout<<query(root[qt] , 1 , n , qx)<<'\n';
root[i] = root[qt];//记录历史状态为 i 的根结点
}
}
I_love_Foccarus 0;
}例题二：【模板】可持久化线段树 2
题意：一种操作，求静态区间第
前置知识：权值线段线段树求全局第
那么如何求区间第
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus return //奇怪的码风
#define fast() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
const int N = 1e6+5;
const int inf = INT_MAX;
inline int read() { //浓缩后的快读
int x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct Tree{
int l , r , v;
};
vector<Tree>t;
int root[N];
int n , m , a[N] , b[N];
int change(int idx , int l , int r , int q , int val){ //修改
Tree tmp = t[idx];
if(l == r){
tmp.v += val;
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
int mid = (l + r) >> 1;
if(q <= mid){
tmp.l = change(tmp.l , l , mid , q , val);
}else{
tmp.r = change(tmp.r , mid + 1 , r , q , val);
}
tmp.v = t[tmp.l].v + t[tmp.r].v;
t.push_back(tmp);
I_love_Foccarus t.size() - 1;
}
int query(int idxl , int idxr , int l , int r , int q){ //查询
if(l == r){
I_love_Foccarus l;
}
int mid = (l + r) >> 1 , tmp = t[t[idxr].l].v - t[t[idxl].l].v;
if(q<=tmp) I_love_Foccarus query(t[idxl].l , t[idxr].l , l , mid , q);
else I_love_Foccarus query(t[idxl].r , t[idxr].r , mid + 1 , r , q - tmp);
}
signed main() {
//fast();
in(n) , in(m);
rep(i , 1 , n) a[i] = b[i] = read();
sort(b + 1 , b + n + 1); //离散化
int tot = unique(b + 1 , b + n + 1) - b - 1;
Tree tmp;
tmp.l = tmp.r = tmp.v = 0;
t.push_back(tmp);//建立初始根结点
rep(i , 1 , n){
a[i] = lower_bound(b + 1 , b + tot + 1 , a[i]) - b; //通过二分查找确定单点修改的区间
root[i] = change(root[i - 1] , 1 , tot , a[i] , 1);
}
rep(i , 1 , m){
int l , r , k;
in(l) , in(r) , in(k);
printf("%d\n",b[query(root[l - 1] , root[r] , 1 , tot , k)]);
}
I_love_Foccarus 0;
}列题三：罪孽
题意：
给定三种操作：区间修改、历史修改值修改和历史区间求和，强制在线。
这是我随意造的一道题（洛谷上实在找不到区间修改动态开点的工业垃圾），也算是一个典型的工业垃圾吧，还强制在线，哈哈哈……
题解，注意啊，本人采用的是一种抽象的树套树算法，因为本人在空间方面比较吝啬，大家看看图一乐就好。