树论--线段树篇
题单介绍
# 洛谷斗树场--线段树篇
线段树是一个应用极为广泛的高级数据结构，具有极广的应用范围，且可衍生出许多算法，在这里，你将认识到各种线段树的神仙操作，来到这里就是~~命运石之门~~缘分，启程吧，少年。
## 线段树入门
线段树的基础，基本为单点修改、查询及区间修改、查询，可能会涉及到简单的延迟标记维护，之后的大多数线段树都讲建立在普通线段树的基础上，只需要时刻牢记线段树的特性，这些挫折将迎刃而解，在这里，你可能会遭遇到许许多多程序崩溃的情况，不要激动，正常现象，码线段树的过程就是不断码$bug$的过程。
[P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)（线段，线段，线段树！！！）
[P1886 滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886)（$\forall x=数据结构,线段树=x$）
[P4588 [TJOI2018]数学计算](https://www.luogu.com.cn/problem/P4588)（尝试转化为可用线段树维护的问题）
[P5142 区间方差](https://www.luogu.com.cn/problem/P5142)（需要推个小柿子）
[P4145 上帝造题的七分钟 2 / 花神游历各国](https://www.luogu.com.cn/problem/P4145)（在一些难以用$lztage$优化时，请不要吝啬你的时间）
[ GSS1 - Can you answer these queries I
](https://www.luogu.com.cn/problem/SP1043)（区间最大字段和，经典问题）
## 线段树进阶
恭喜你，少年！经过入门考核的磨练，相信你已经基本掌握了线段树的实现方式，明白了基本原理，见识到了线段树的基本$bug$，并学会了初步处理。在本次试炼中，请留意**延迟标记**的实现，并尝试提高自己的$debug$能力。线段树之路的第一个挫折。ps：在遇到区间修改，单点查询且不能维护延迟标记时，可以尝试利用差分或前缀和的思想，讲问题转化为单点修改，区间查询。
[P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)（线段，线段，线段树！！！）
[P2184 贪婪大陆](https://www.luogu.com.cn/problem/P2184)（将区间修改转化为单点修改）
[P1438 无聊的数列](https://www.luogu.com.cn/problem/P1438)（ko no 差分 da！！！）
[P6327 区间加区间sin和](https://www.luogu.com.cn/problem/P6327)（TLE¿试试$lztage$）
## $boss$战——线段树大触
您已经是$dalao$辣！！！
[U96354 魔能阵列](https://www.luogu.com.cn/problem/U96354)（尝试分析题目中的特殊性质）
[P2572 [SCOI2010]序列操作](https://www.luogu.com.cn/problem/P2572)（$lztage$的魅力）
[P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)（注意两个儿子之间的互相影响）
---
$\huge EX$
[P6242 【模板】线段树 3](https://www.luogu.com.cn/problem/P6242)（吉老师线段树）
## 权值线段树
权值线段树又叫值域线段树，以值域为基础，一般用来统计某个值的次数，同样是线段树的经典形式，在这里，你将更加深刻地了解线段树，运用将更加灵活。主席树的起点。（注意离散化）
[P1908 逆序对](https://www.luogu.com.cn/problem/P1908)（偏序问题基础）
[P1637 三元上升子序列](https://www.luogu.com.cn/problem/P1637)（同上）
[P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369)（$\forall x=数据结构,线段树=x$）
## 扫描线
线段树不止可以解决区间问题，甚至还可以解决几何问题，通常用来求周长、面积等相关问题，扩展到扫描面甚至可以求体积问题（升 维 打 击）
[P5490 【模板】扫描线](https://www.luogu.com.cn/problem/P5490)（面积并）
[P1856 [USACO5.5]矩形周长Picture](https://www.luogu.com.cn/problem/P1856)（周长…并¿）
## 可持久化线段树（主席树）
如果线段树是高级数据结构中的经济基础，那么主席树应该就是高级数据结构中的上层建筑，应用较为广泛，线段树必学之一。又叫函数式线段树，利用前缀和的思想可以快速取出建立在区间$[l,r]$上的线段树。
[P3919 【模板】可持久化线段树 1（可持久化数组）](https://www.luogu.com.cn/problem/P3919)（线段，线段，线段树！！！）
[P3834 【模板】可持久化线段树 2](https://www.luogu.com.cn/problem/P3834)（线段，线段，线段树！！！）
[P1383 高级打字机](https://www.luogu.com.cn/problem/P1383)（学会处理主席树中个历史版本的关系)
## 线段树综合
~~好久没更了~~
实话实说，全球各大小赛事中，考到裸线段树的题目说不多也不多，说不少也不少，近几年ccf仅CSP、noip这类全国统一试题就设计了3-5个裸线段树的题目，如：[ [NOIP2017 提高组] 列队](https://www.luogu.com.cn/problem/P3960)、[ [CSP-S 2021] 廊桥分配 ](https://www.luogu.com.cn/problem/P7913)、[ [NOIP2013 提高组] 火柴排队 ](https://www.luogu.com.cn/problem/P1966)，但无论题目怎么出，作为数据结构，仅依靠单打独斗的线段树必然没有前途（），其对于其他算法的结合以起到的优化作用同样必不可少，某些问题失去了线段树的处理，再强大的算法也会无能为力。
[P7453 [THUSCH2017] 大魔法师](https://www.luogu.com.cn/problem/P7453)
[P1848 [USACO12OPEN]Bookshelf G](https://www.luogu.com.cn/problem/P1848)
update 21/12/8 树套树移至新[题单](https://www.luogu.com.cn/training/131115)
update 22/4/13 增添新版块 **线段树综合**，迁入P2916,P3415,P1505,P7453，P4216共 **5** 题。移除若干过时题目。