BF的数据结构题单-省选树形数据结构 1

Part 2

由于 SX 的数据结构太多了，所以我会不断更新。

本题单涉及的内容包括：线段树，可持久化线段树，平衡树，线段树合并/分裂，cdq分治/树套树。

提高难度的题单

省选树形数据结构题单 2

省选根号数据结构题单

其他的数据结构未来也会不断的加入，可能会建更多的题单。

维护复杂信息

也许需要配合一些别的技巧。

P5524 [Ynoi2012]NOIP2015洋溢着希望
P4198 楼房重建
P1712 [NOI2016]区间
P4097 [HEOI2013]Segment
P3792 由乃与大母神原型和偶像崇拜
P5607 [Ynoi2013]无力回天NOI2017
P2605 [ZJOI2010]基站选址
P3285 [SCOI2014]方伯伯的OJ
主席树

可持久化线段树又名主席树，可以解决一些静态的二维问题。
P3834 【模板】可持久化线段树 1（主席树）
P4587 [FJOI2016]神秘数
P4602 [CTSC2018]混合果汁
P3168 [CQOI2015]任务查询系统
P2633 Count on a tree
P2839 [国家集训队]middle

线段树的合并与分裂

线段树合并与分裂是线段树的常用技巧。

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
P5494 【模板】线段树分裂
P1600 天天爱跑步
CF600E Lomsat gelral
P4577 [FJOI2018]领导集团问题
P2824 [HEOI2016/TJOI2016]排序
P4770 [NOI2018]你的名字
树套树/cdq分治/整体二分

这几个方法基本是互通的，大部分的题目都可以互相替换。

~~严厉斥责最后一题的卡常行为~~

P3380 【模板】二逼平衡树（树套树）
P3810 【模板】三维偏序（陌上花开）
P1975 [国家集训队]排队
P2617 Dynamic Rankings
P3332 [ZJOI2013]K大数查询
P3242 [HNOI2015]接水果
P3759 [TJOI2017]不勤劳的图书管理员
P4093 [HEOI2016/TJOI2016]序列
P5621 [DBOI2019]德丽莎世界第一可爱
P5445 [APIO2019]路灯
CF1093E Intersection of Permutations
P4690 [Ynoi2016]镜中的昆虫
平衡树

其实现在只能用平衡树做的题并不多
P6136 【模板】普通平衡树（数据加强版）
P3391 【模板】文艺平衡树
P1110 [ZJOI2007]报表统计
P2042 [NOI2005]维护数列
P3165 [CQOI2014]排序机械臂
P3987 我永远喜欢珂朵莉~
P3215 [HNOI2011]括号修复 / [JSOI2011]括号序列
P4567 [AHOI2006]文本编辑器