当前位置：首页 > news >正文

可持久化线段树算法详解

news 2026/7/24 13:41:39

一、什么是可持久化数据结构

1.1 基本概念

可持久化（Persistent）是指在数据结构被修改后，仍然能够保留修改前的历史版本，并能够在这些历史版本上进行查询操作。

1.2 应用场景

区间第k大/小查询（主席树）
二维/三维偏序问题
版本控制系统
时间轴查询问题

二、可持久化线段树（主席树）

2.1 核心思想

每次修改只创建新路径上的节点，复用未修改的子树
通过根节点数组记录每个版本的入口

2.2 数据结构设计

struct Node { int l, r; // 左右儿子编号 int val; // 节点存储的值 // 根据具体问题可添加更多字段 }; const int MAXN = 1e5 + 10; const int LOG = 20; // log2(MAXN) Node tree[MAXN * LOG * 4]; // 节点池 int roots[MAXN]; // 各个版本的根节点 int node_cnt = 0; // 节点计数器

基础操作实现

3.1 节点创建

// 创建新节点（可复用旧节点部分信息） int new_node(int old = 0) { node_cnt++; if (old) tree[node_cnt] = tree[old]; else tree[node_cnt].l = tree[node_cnt].r = tree[node_cnt].val = 0; return node_cnt; }

3.2 建树（初始化版本0）

int build(int l, int r) { int p = new_node(); if (l == r) { // 初始化叶子节点 return p; } int mid = (l + r) >> 1; tree[p].l = build(l, mid); tree[p].r = build(mid + 1, r); return p; }

3.3 单点更新

// 在版本old_root基础上，将位置pos的值增加val int update(int old_root, int l, int r, int pos, int val) { int p = new_node(old_root); if (l == r) { tree[p].val += val; return p; } int mid = (l + r) >> 1; if (pos <= mid) { tree[p].l = update(tree[old_root].l, l, mid, pos, val); } else { tree[p].r = update(tree[old_root].r, mid + 1, r, pos, val); } // 向上更新 tree[p].val = tree[tree[p].l].val + tree[tree[p].r].val; return p; }

经典应用：静态区间第k小

4.1 问题描述

给定长度为n的数组和m个查询，每个查询求区间[l, r]中第k小的数。

4.2 算法步骤

步骤1：离散化

vector<int> nums = original_array; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 获取离散化后的值 int get_id(int x) { return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1; }

步骤2：构建版本序列

roots[0] = build(1, nums.size()); for (int i = 1; i <= n; i++) { int id = get_id(original_array[i-1]); roots[i] = update(roots[i-1], 1, nums.size(), id, 1); }

步骤3：区间查询

int query(int root_l, int root_r, int l, int r, int k) { if (l == r) return l; int mid = (l + r) >> 1; int left_cnt = tree[tree[root_r].l].val - tree[tree[root_l].l].val; if (k <= left_cnt) { return query(tree[root_l].l, tree[root_r].l, l, mid, k); } else { return query(tree[root_l].r, tree[root_r].r, mid + 1, r, k - left_cnt); } } // 查询区间[l, r]的第k小 int ans_id = query(roots[l-1], roots[r], 1, nums.size(), k); int ans = nums[ans_id - 1]; // 还原原始值

4.3 时间复杂度分析

建树：O(n log n)

每次更新：O(log n)

每次查询：O(log n)

空间复杂度：O(n log n)

五、进阶应用

5.1 带修改的可持久化线段树（树状数组套线段树）

// 使用树状数组维护外层，每个节点是一棵线段树 void modify(int x, int pos, int val) { for (; x <= n; x += x & -x) { roots[x] = update(roots[x], 1, len, pos, val); } } int query_prefix(int x, int l, int r, int k) { // 查询前缀[1, x]的信息 }

5.2 可持久化权值线段树求区间不同数个数

// 记录每个值最后一次出现的位置 // 在位置i插入时，在版本i中： // 1. 删除该值上次出现的位置 // 2. 在位置i插入该值 六、模板代码（完整实现） cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; const int LOG = 20; struct Node { int l, r, sum; } tree[MAXN * LOG]; int roots[MAXN], a[MAXN], nums[MAXN]; int node_cnt = 0, n, m; int build(int l, int r) { int p = ++node_cnt; if (l == r) return p; int mid = (l + r) >> 1; tree[p].l = build(l, mid); tree[p].r = build(mid + 1, r); return p; } int update(int pre, int l, int r, int pos) { int p = ++node_cnt; tree[p] = tree[pre]; tree[p].sum++; if (l == r) return p; int mid = (l + r) >> 1; if (pos <= mid) { tree[p].l = update(tree[pre].l, l, mid, pos); } else { tree[p].r = update(tree[pre].r, mid + 1, r, pos); } return p; } int query(int u, int v, int l, int r, int k) { if (l == r) return l; int mid = (l + r) >> 1; int left_sum = tree[tree[v].l].sum - tree[tree[u].l].sum; if (k <= left_sum) { return query(tree[u].l, tree[v].l, l, mid, k); } else { return query(tree[u].r, tree[v].r, mid + 1, r, k - left_sum); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); nums[i] = a[i]; } // 离散化 sort(nums + 1, nums + n + 1); int len = unique(nums + 1, nums + n + 1) - nums - 1; // 建树 roots[0] = build(1, len); // 构建版本 for (int i = 1; i <= n; i++) { int id = lower_bound(nums + 1, nums + len + 1, a[i]) - nums; roots[i] = update(roots[i-1], 1, len, id); } // 查询 while (m--) { int l, r, k; scanf("%d%d%d", &l, &r, &k); int id = query(roots[l-1], roots[r], 1, len, k); printf("%d\n", nums[id]); } return 0; }

练习题推荐

基础题目

1. 静态区间第k小

POJ 2104 K-th Number
http://poj.org/problem?id=2104

SPOJ MKTHNUM
https://www.spoj.com/problems/MKTHNUM/

洛谷 P3834 【模板】可持久化线段树 2
https://www.luogu.com.cn/problem/P3834

2. 区间不同数个数

SPOJ DQUERY - D-query
https://www.spoj.com/problems/DQUERY/

HDU 3333 Turing Tree
http://acm.hdu.edu.cn/showproblem.php?pid=3333

进阶题目

1. 带修改的可持久化线段树

HDU 4348 To the moon
http://acm.hdu.edu.cn/showproblem.php?pid=4348

BZOJ 1901 Dynamic Rankings
https://hydro.ac/d/bzoj/p/1901

洛谷 P2617 Dynamic Rankings
https://www.luogu.com.cn/problem/P2617

2. 二维问题

Codeforces 813E Army Creation
https://codeforces.com/problemset/problem/813/E

HDU 5919 Sequence II
http://acm.hdu.edu.cn/showproblem.php?pid=5919

3. 树上问题

SPOJ COT - Count on a tree
https://www.spoj.com/problems/COT/

BZOJ 2588 Count on a tree
https://hydro.ac/d/bzoj/p/2588

洛谷 P2633 Count on a tree
https://www.luogu.com.cn/problem/P2633

4. 综合应用

Codeforces 840D Destiny
https://codeforces.com/problemset/problem/840/D

HDU 5799 This world need more Zhu
http://acm.hdu.edu.cn/showproblem.php?pid=5799

专项训练

1. 可持久化并查集

BZOJ 3673 可持久化并查集
https://hydro.ac/d/bzoj/p/3673

洛谷 P3402 可持久化并查集
https://www.luogu.com.cn/problem/P3402

2. 可持久化平衡树

洛谷 P3835 【模板】可持久化平衡树
https://www.luogu.com.cn/problem/P3835

BZOJ 3674 可持久化并查集加强版
https://hydro.ac/d/bzoj/p/3674

八、注意事项

1.空间管理
2.预估节点总数：操作次数 × log(n)
3.使用动态开点避免MLE
4.离散化处理
5.注意边界情况
6.保持值域连续
7.版本控制
8.明确每个版本根节点的含义
9.注意版本索引从0还是1开始

总结

可持久化线段树是一种功能强大的数据结构，通过"部分复制"的思想实现了版本管理。掌握其原理和实现，能够解决许多复杂的区间查询问题，是算法竞赛中的重要工具。

好水的主席树板子题

一：https://www.luogu.com.cn/problem/P4587

P4587 [FJOI2016] 神秘数

用可持久化线段树维护区间小于等于 � 的值之和。

可以证明每次计算答案是 log 级别的。

#include<bits/stdc++.h> #define wk(x) write(x),putchar(' ') #define wh(x) write(x),putchar('\n') #define int long long #define INF 1e15 #define L (tree[p].l) #define R (tree[p].r) #define MID ((l+r)>>1) #define N 500005 using namespace std; int n,m,k,jk,ans,sum,num,cnt,tot; int head[N],dis[N],vis[N],wis[N],f[N],Root[N]; void read(int &x) { // return; } void write(int x) { // return; } struct SUG{ struct T{ int l,r,ans; }tree[(N<<2)*20]; void push_down(int p){ tree[p].ans=tree[L].ans+tree[R].ans; } void ADD(int &p,int l,int r,int x,int y){ tree[++cnt]=tree[p];p=cnt; if(x<=l&&r<=y){ tree[p].ans+=y;return; } if(MID>=x) ADD(L,l,MID,x,y); if(MID<y) ADD(R,MID+1,r,x,y); push_down(p); } int query_add(int p,int l,int r,int x,int y){ if(x<=l&&r<=y){return tree[p].ans;} int zz=0; if(MID>=x) zz+=query_add(L,l,MID,x,y); if(MID<y) zz+=query_add(R,MID+1,r,x,y); push_down(p);return zz; } }T; //struct H{ // int l,r,t,id; //}q[N]; // //bool cmp(const H &a,const H &b){ // return a.l/sz==b.l/sz?a.r/sz==b.r/sz?a.t<b.t:a.r<b.r:a.l<b.l; //} signed main() { read(n); for(int i=1;i<=n;i++) read(dis[i]);Root[0]=++cnt; for(int i=1;i<=n;i++) T.ADD(Root[i]=Root[i-1],1,INF,dis[i],dis[i]); read(m);while(m--){ int l,r,ans=1;read(l),read(r); while(1){ int z=T.query_add(Root[r],1,INF,1,ans)-T.query_add(Root[l-1],1,INF,1,ans); if(z>=ans) ans=z+1;else break; }wh(ans); } return 0; }

二：https://www.luogu.com.cn/problem/P11807

P11807 [PA 2017] 抄作业

~~「你抄就抄吧，但是稍微改改，别和我的一模一样就行。」~~

容易想到用哈希比较，得出第一个不同的位置。

于是可以在线段树上二分。由于每次只修改一个点，故不难想到可持久化线段树，每次新开一条路。

#include<bits/stdc++.h> #define wk(x) write(x),putchar(' ') #define wh(x) write(x),putchar('\n') #define int long long #define L (tree[p].l) #define R (tree[p].r) #define MID ((l+r)>>1) #define N 500005 using namespace std; const int G=1331; const int mod=998244353; int n,m,k,jk,ans,sum,num,cnt,tot; int head[N],dis[N],vis[N],wis[N],f[N],Root[N]; void read(int &x) { // return; } void write(int x) { // return; } struct SUG{ struct T{ int l,r; unsigned long long ans; }tree[(N<<2)*20]; void push_down(int p,int len){ tree[p].ans=tree[L].ans*wis[len]+tree[R].ans; return; } void build(int &p,int l,int r){ tree[++cnt]=tree[p];p=cnt; if(l==r){tree[p].ans=dis[l];return;} build(L,l,MID);build(R,MID+1,r); push_down(p,MID-l+1);return; } void ADD(int &p,int l,int r,int x,int z){ tree[++cnt]=tree[p];p=cnt; if(l==r){tree[p].ans=z;return;} if(MID>=x) ADD(L,l,MID,x,z); else ADD(R,MID+1,r,x,z); push_down(p,MID-l+1);return; } int query_add(int p,int p1,int l,int r){ if(l==r) return tree[p].ans<tree[p1].ans?1:-1; if(tree[tree[p].l].ans!=tree[tree[p1].l].ans) return query_add(tree[p].l,tree[p1].l,l,MID); else if(tree[tree[p].r].ans!=tree[tree[p1].r].ans) return query_add(tree[p].r,tree[p1].r,MID+1,r); else return 0; } }T; struct P{int id;}q[N]; bool cmp(P a,P b){ int Get=T.query_add(Root[a.id],Root[b.id],1,n); return ((Get==0)?a.id<b.id:(Get==-1?0:1)); } signed main() { read(n);read(m);wis[0]=1; for(int i=1;i<=n;i++) read(dis[i]),wis[i]=wis[i-1]*G%mod; T.build(Root[1]=++cnt,1,n);q[1].id=1; for(int i=2,x,y;i<=m;i++){ read(x),read(y);q[i].id=i; T.ADD(Root[i]=Root[i-1],1,n,x,y); } sort(1+q,1+q+m,cmp); for(int i=1;i<=m;i++) wk(q[i].id); return 0;

查看全文

http://www.jsqmd.com/news/568184/