线段树

线段树是一种基于树状数组的数据结构，用于高效地处理区间查询问题。线段树将一个区间划分成若干个小区间，每个小区间对应树状数组中的一个节点。线段树的每个节点都维护一个区间的信息，如区间和、最大值、最小值等。

线段树的构建过程是将一个区间递归地分成两个子区间，并对子区间递归构建线段树，直到区间长度为1。线段树的叶子节点对应区间中的单个元素。线段树中每个节点对应的区间可以通过节点的位置计算得到。

线段树支持的操作包括区间查询和单点修改。区间查询的过程是从根节点开始递归，查询覆盖区间的所有节点，并将每个节点的信息合并。单点修改的过程是从叶子节点开始递归，依次修改每个节点的信息，并将信息向上传递。

线段树的时间复杂度为O(log n)，其中n是区间长度。线段树的空间复杂度为O(n)。