线段树是一种常用于维护区间信息的数据结构。

线段树可以在 的时间复杂度内执行诸如单点更新、区间更新和区间查询（区间和、区间最大值、区间最小值）等操作。