线段树解题技巧

前言

线段树是一种在 \(\log\) 时间内维护区间信息的数据结构，其维护的信息通常具有区间可加性。

区间可加性，也就是由区间 \(A\) 和区间 \(B\)，可以推出 \(A\cup B\)。

上面说到的区间，指的是区间内维护的信息。

如区间和，区间平方和，区间最值，区间最大子段，区间最长连续子段，这类问题就是具有区间可加性的。

关于线段树维护的题目，分为两类，一类是好维护的，一类是不好维护的，体现在修改与查询的关系并不大。下面分这两类进行分析。

好维护

好维护的信息通常是由修改可以推出查询，比如修改是将一个区间加上某个数，查询是查区间和，这时可以直接由修改推出查询。