线段树

区间查询

线段树可以维护具有结合律的信息。

区间修改 区间查询

加上修改后应当满足的前提是

1. 我们可以维护一个封闭的集合 \(\mathcal{S}\)，使得任一操作 \(o\in\mathcal{S}\)，且 \(\mathcal{S}\) 对于复合封闭，即对任意 \(u,v\in\mathcal{S}\)，有 \(u\circ v\in\mathcal{S}\)。
2. 对于任意一个区间 \(s\) 和一个操作 \(o\)，我们需要足够快地求出 \(o\) 作用在 \(s\) 上后，\(s\) 区间的答案。

需要特别注意的一点 \(\mathcal{S}\) 必须对任意复合严格的封闭，不能存在任何的特例，因为在线段树的 pushdown 过程中任意的 \(u,v\in\mathcal{S}\) 都可能需要被进行复合操作。上述的条件是充分且必要的。

例如区间加区间求和，对于任意两个区间加操作 \(\operatorname{ADD}(u),\operatorname{ADD}(v)\)，它们的复合我们可以表示为 \(\operatorname{ADD}(u+v)\)，满足条件 1；
对于一个 \(\operatorname{ADD}(u)\) 作用在区间 \(s\) 后，\(\operatorname{ANS}(s')=\operatorname{ANS}(s)+|s|u\)，可以快速求出，满足条件 2。

例题

区间修改 单点查询

区间修改区间查询的约束 2 过于强，对于比较复杂的题很多时候简单分析就可以否决 Polylog 的可能，直接排除了使用线段树维护。

但是对于单点查询，满足约束 1 即可，很多时候复杂的修改也能用线段树维护。因此对于区间修改单点查询的题目，无论多么复杂，应当先尝试线段树。

例题

可持久化

能用上一般都看得出来，很多时候作为一道题的一部分，下面会贴一些比较有意思的应用。

[TODO]

分块