线段树
为什么需要线段树?
-
如果我们想知道数组
arr的任意区间和sum(arr[i:j]),那么维护 前后缀和 是一个不错的选择=> 只需预处理一次、之后所有查询仅需 \(O(1)\)
-
但如果数组中的值需要 被修改呢 ?此时需要重新计算 所有 前后缀和
-
此外,前后缀和也不能提供对区间 最大/最小值 的快速查询支持
-
-
线段树(Segment Tree)就是为维护这类 需要动态修改的区间信息 设计的,可以在 \(O(\log{N})\) 内实现单点修改、单点查询、区间修改,以及区间查询
本文仅介绍最基本的线段树实现(递归建树 + 懒更新)