Segment Tree 线段树

线段树解决的是「区间和」的问题，且该「区间」会被修改

一个区间的例子是对于 nums = [1, 2, 3, 4, 5] 多次求某些区间的和，是不是首先想到了利用「前缀和」。

但是如果 nums 会被修改呢？比如：

• 把第 i 个元素修改成 x
• 把第 i 个元素增加 x
• 把区间 [i, j] 内的元素都增加 x

此时，如果我们再使用「前缀和」，就没那么高效了。因为每一次更新，前缀和数组必须也随之更新，时间复杂度为 O(n)。

既然「前缀和」在这种场景下没那么高效了，所以就有了今天要介绍的「线段树」

线段树

nums = [1, 2, 3, 4, 5] 对应的线段树如下所示：