主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
【深入练习】数据结构
最后更新于 2025-07-23 21:10:05
作者
_sst_
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
# 可持久化数据结构 ## 线段树 ### 基本原理 本质在于：在修改时不直接修改原线段树，而是开一个新的线段树记录修改后的信息，单次被修改的线段树节点至多只有 $O(\log_2 n)$ 个，不修改的节点可以直接使用原树的，这需要维护的结构无需记录父亲，线段树满足这一特性。 ### 做题技巧 一般情况下，线段树可持久化都是为了方便查询历史版本，所以如果我们可以把查询离线下来，直接维护线段树，边修改边查询，那我们就可以使用可持久化线段树来在线地做查询。 ### [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839) 显然二分。 中位数有一个经典的套路，二分答案后把 $\ge mid$ 的设为 $1$，否则为 $-1$，若区间和 $\ge 0$，则中位数 $\ge mid$。 由于本题的左右端点不确定，而我们肯定尽量希望区间和最大，可以使用线段树维护，找到 $[a,b]$ 的最大后缀和以及 $[c,d]$ 的最大前缀和即可。 但是我们显然不可能每次暴力修改线段树，而如果提前对每个 $mid$ 开好一棵线段树也是无法接受的。 考虑线段树可持久化，对每个 $mid$ 开一棵线段树，其中第 $i$ 棵线段树是在第 $i-1$ 棵线段树的基础上得到的。 ### [P4899 [IOI 2018] werewolf 狼人](https://www.luogu.com.cn/problem/P4899) 设变身点为 $u$，则我们需要从 $s$ 仅走 $[l,n]$ 内的点走到 $u$，且从 $y$ 仅走 $[1,r]$ 内的点走到 $u$。 若存在一个这样的 $u$，即从 $s$ 出发仅走 $[l,n]$ 内点能到达的点与从 $t$ 出发仅走 $[1,r]$ 内点能到达的点存在交集。 容易想到 Kruskal 重构树，把问题转化成两棵树内点是否有交。 转化到 $\rm DFS$ 序上，然后可以转化到二维平面上，进行区间求和，使用可持久化线段树容易解决。 # 分块 ## 做题技巧 常见的分块分为两种：对序列分块以及对询问分块。
正在渲染内容...
点赞
0
收藏
0
