线段树(Segment-Tree)
简介
线段树（Segment Tree）是一种二叉树形数据结构，1977 年由 Jon Louis Bentley 发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。
与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。
对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。
线段树结构示意（其存储的线段显示在图片的下方）
一个包含 nn 个区间的线段树，空间复杂度为 $O(n)$，查询的时间复杂度则为 $O(log{n}+k)$，其中 k 是符合条件的区间数量。
此数据结构亦可推广到高维度。