发现每一次修改操作最多影响 自上而下一条链上的 log n个节点。
则可每次修改操作都新建 log n个节点。
不同版本 的根不同。
查询操作 与普通线段树一致
函数参数中L, R 代表当前区间左右端点。
//知识点:可持久化线段树
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#define ls (t[now].lson)
#define rs (t[now].rson)
#define ll long long
const int MARX = 1e6 + 10;
//=============================================================
struct Node
{
int lson, rson, val;
} t[MARX << 5];
int N, M, Original[MARX];
int NodeNum, Root[MARX];
//=============================================================
inline int read()
{
int f = 1, w = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ ‘0‘);
return f * w;
}
void Build(int &now, int L, int R)
{
now = ++ NodeNum;
if(L == R) {t[now].val = Original[L]; return ;}
int mid = (L + R) >> 1;
Build(ls, L, mid); Build(rs, mid + 1, R);
}
//修改操作，除目标位置外 直接继承历史版本。
void Modify(int Pre, int &now, int L, int R, int Pos, int Val)
{
now = ++ NodeNum;
ls = t[Pre].lson, rs = t[Pre].rson, t[now].val = t[Pre].val; //继承信息
if(L == R) {t[now].val = Val; return;}
int mid = (L + R) >> 1;
if(Pos <= mid) Modify(t[Pre].lson, ls, L, mid, Pos, Val);
else Modify(t[Pre].rson, rs, mid + 1, R, Pos, Val);
}
//单点查询。
int Query(int now, int L, int R, int Pos)
{
if(L == R) return t[now].val;
int mid = (L + R) >> 1;
if(Pos <= mid) return Query(ls, L, mid, Pos);
return Query(rs, mid + 1, R, Pos);
}
//=============================================================
int main()
{
N = read(), M = read();
for(int i = 1; i <= N; i ++) Original[i] = read();
Build(Root[0], 1, N);
for(int i = 1; i <= M; i ++)
{
int Pre = read(), Opt = read(), Pos = read(), Val;
if(Opt == 1) Val = read(), Modify(Root[Pre], Root[i], 1, N, Pos, Val);
else printf("%d\n", Query(Root[Pre], 1, N, Pos)), Root[i] = Root[Pre];
}
return 0;
}
写在最后
主席树是可持久化线段树的真子集，全称可持久化权值线段树。
在学习主席树之前务必熟练掌握可持久化线段树。
原文：https://www.cnblogs.com/luckyblock/p/12812808.html