线段树

线段树树基于分治思想的二叉树，用来维护区间信息(区间和、区间最大值、区间最小值等等)。可以在$O(logn)$的时间内完成区间信息的查询和修改。

• 线段树中每个叶子结点存储元素本身，非叶子结点存储区间内元素的统计值