可持久化线段树

可持久化线段树算法详解

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

1.1 基本概念

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

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

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

2.1 核心思想

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

2.2 数据结构设计

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

复制代码

基础操作实现

3.1 节点创建

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

复制代码

3.2 建树（初始化版本0）

1. int build(int l, int r) {
2.     int p = new_node();
3.     if (l == r) {
4.         // 初始化叶子节点
5.         return p;
6.     }
7.     int mid = (l + r) >> 1;
8.     tree[p].l = build(l, mid);
9.     tree[p].r = build(mid + 1, r);
10.     return p;
11. }

复制代码

3.3 单点更新

[code]// 在版本old_root基础上，将位置pos的值增加valint 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  1;    int left_cnt = tree[tree[root_r].l].val - tree[tree[root_l].l].val;        if (k  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 > 1;    int left_sum = tree[tree[v].l].sum - tree[tree.l].sum;        if (k

喜欢鼓捣这些软件，现在用得少，谢谢分享！

感谢分享，下载保存了，貌似很强大

东西不错很实用谢谢分享

东西不错很实用谢谢分享

喜欢鼓捣这些软件，现在用得少，谢谢分享！

感谢分享，学习下。

鼓励转贴优秀软件安全工具和文档！

谢谢楼主提供！

鼓励转贴优秀软件安全工具和文档！

感谢分享，学习下。

喜欢鼓捣这些软件，现在用得少，谢谢分享！

感谢发布原创作品，程序园因你更精彩

这个有用。

不错，里面软件多更新就更好了

用心讨论，共获提升！

感谢，下载保存了

感谢发布原创作品，程序园因你更精彩