$$\texttt{线段树}$$

线段树是一种用于维护区间信息的数据结构，可以在 $O(\log n)$ 的复杂度下求出一个大小为 $n$ 的数组的区间信息（如区间和、区间最大值等），也可以在同样时间复杂度下实现单点修改和区间修改等操作。

基本结构：

线段树与树状数组