线段树知识点与例题总结

一、相关教程资源

线段树详解与实现

线段树与树状数组的视频教程，非常清晰，强烈推荐

二、单点修改

\(AcWing\) \(1275\). 最大数[单点修改区间查询]

\(AcWing\) \(245\). 你能回答这些问题吗[单点修改区间查询]

\(AcWing\) \(246\). 区间最大公约数[单点修改区间查询+差分+更相减损数]

三、区间修改

\(HDU\) \(1698\) \(Just\) \(a\) \(Hook\)[黄海补充+区间修改统一值+区间查询]

\(HDU\) \(3577\) \(Fast\) \(Arrangement\) [黄海补充+线段树+区间修改+维护最大值]

\(POJ\) \(3264\) \(Balanced\) \(Lineup\)[黄海补充+线段树+维护最大值、最小值]

\(AcWing\) \(243\). 一个简单的整数问题[区间增加一个值+区间查询]

\(HDU\) \(3333\) \(Turing\) \(Tree\) [黄海补充+线段树(树状数组)+离线操作+数字去重求区间和]

\(POJ\) \(2828\) \(Buy\) \(Tickets\)[黄海补充+线段树+二分]

四、扫描线法

\(AcWing\) \(1228\). 油漆面积[扫描线+线段树，黄海补充]

\(AcWing\) \(247\). 亚特兰蒂斯

\(AcWing\) \(1277\). 维护序列

五、线段树优化建图

Legacy CodeForces - 787D

六、线段树维护树上信息

POJ 3321 Apple Tree [\(dfs\)序求子树节点和]

据说线段树还可以应用bfs序，目前还没有找到合适的练习题，挖坑待填吧~

dfs序基础讲解（小白版）

七、线段树维护区间可合并信息

\(POJ\) \(2777\) \(Count\) \(Color\)

八、线段树维护区间不可合并信息（暴力计算）

\(GSS4\) - \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(IV\) [暴力开方]

\(P4145\) 上帝造题的七分钟 \(2\) / 花神游历各国
这个其实就是上面那道题，一模一样，输出有点差别而已。

\(CF438D\) \(The\) \(Child\) \(and\) \(Sequence\)[暴力取模]

九、线段树维护最大子段和

\(GSS1\) - \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(I\) [区间最大子段和]
\(GSS3\) - \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(III\)[区间最大子段和+单点修改]
\(GSS5\) - \(Can\) \(you\) \(answer\) \(these\) \(queries\) \(V\)[有范围限制的区间最大子段和]

十、线段树与思维

\(HDU\) \(5649\) \(DZY\) \(Loves\) \(Sorting\)

十一、线段树分裂与合并

\(P5494\) 【模板】线段树分裂

\(P4556\) [\(Vani\)有约会]雨天的尾巴 /【模板】线段树合并

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

推荐视频

\(AcWing\) \(255\). 第\(K\)小数

\(HDU\) \(5280\) \(Lights\)