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

可持久化数据结构

可持久化线段树

别名:主席树

应用:用于查询指定的闭区间 \([l,r]\) 内的第 \(k\) 小值。

思想:通过新开节点,把被修改的那条链存下来,得到一个新的根,再与之前的主席树建立关系。

实现:动态开点,并保存每个节点的左右儿子编号。记录左右儿子,并保存插入每个数的时候的根节点就可以实现持久化了。

本质:与线段树差不多,只需要找到插入 \(r\) 时的根节点版本,然后用普通线段树就可以做了。还需要联系前缀和,以在区间查询上达到 \(O(1)\) 的复杂度。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=1e9;
struct Node{int l,r,val;
}tr[N<<5];
int root[N],top;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
void build(int &node,int l,int r,int k){if(!node) node=++top;tr[node].val++;if(l==r) return;int mid=(l+r)>>1;if(k<=mid) build(tr[node].l,l,mid,k);else build(tr[node].r,mid+1,r,k);
}
int query(int a,int b,int l,int r,int k){if(l==r) return l;int mid=(l+r)>>1;int t=tr[tr[b].l].val-tr[tr[a].l].val;if(k<=t) return query(tr[a].l,tr[b].l,l,mid,k);else return query(tr[a].r,tr[b].r,mid+1,r,k-t);
}
void merge(int &x,int y){if(!x||!y){x+=y;return;}tr[x].val+=tr[y].val;merge(tr[x].l,tr[y].l);merge(tr[x].r,tr[y].r);
}
int main(){int n,m,l,r,k;n=read(),m=read();for(int i=1;i<=n;i++){k=read();build(root[i],-inf,inf,k);}for(int i=2;i<=n;i++) merge(root[i],root[i-1]);while(m--){l=read(),r=read(),k=read();printf("%d\n",query(root[l-1],root[r],-inf,inf,k));}return 0;
}

例题:P3919 【模板】可持久化线段树 1(可持久化数组),P3834 【模板】可持久化线段树 2

http://www.hskmm.com/?act=detail&tid=23164

相关文章:

  • 2025.10.2——1黄
  • 图的匹配
  • Tarjan 算法
  • Mondriaans Dream题解
  • 网络流 最大流 Dinic 算法
  • 2025.10.2 测试
  • 数学章节总结
  • 软件工程_作业一
  • CF VP 记录
  • LabVIEW与PLC 汽车驻车制动自动调整 - 实践
  • 04. 布局管理
  • 关于安装博客园皮肤中有关于配置音乐播放器的补充(awescnb)
  • AGC VP 记录 2
  • 2025 --【J+S 二十连测】-- 第四套 总结
  • Websocket+cpolar:如何轻松实现服务远程访问? - 教程
  • 如何用C语言实现5种基本的排序算法
  • 函数-装饰器基础知识+推导式
  • VUE - 实战 2
  • QBXT2025S刷题 Day1
  • 2025多校冲刺CSP模拟赛1(螳臂复活祭)
  • mobvista三月之旅(In Peking)
  • 大学生HTML期末大作业——HTML+CSS+JavaScript购物商城(草莓) - 指南
  • P6782 [Ynoi2008] rplexq
  • AT_agc040_b [AGC040B] Two Contests
  • AT_arc084_b [ABC077D] Small Multiple 题目分析
  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好