线段树 (区间查询)

线段树是一种二元樹，可視為树状数组的變種，

线段树是一种将数组存储为树的数据结构。这允许高效地回答数组上的范围查询，同时仍然足够灵活以允许快速修改数组。
这包括查找连续数组元素a[l \dots r] 的总和，或在O(\log n) 时间内找到此类范围内的最小元素（范围最值查询）。在回答此类查询之间，线段树允许通过替换一个元素甚至更改整个子段的元素来修改数组（例如，将所有元素a[l \dots r] 分配给任何值，或为子段中的所有元素增加一个值）。

通常，线段树是一种非常灵活的数据结构，可以用它解决大量问题。此外，还可以应用更复杂的操作并回答更复杂的查询。特别是，线段树可以轻松推广到更大的维度。例如，使用二维线段树，只需O(\log^2 n) 时间即可回答给定矩阵中某个子矩形的总和或最小值查询。线段树的一个重要特性是它们只需要线性量的内存，通常需要4n个顶点来处理大小为n的数组。。

參考資料