前缀和 树状数组 线段树的区别

转载请注明出处：https://hts0000.github.io/

欢迎与我联系：hts_0000@sina.com

时间复杂度区别

• 求区间和时间复杂度

• 更新或增加时间复杂度

线段树时间复杂度与树状数组一样都为O(logn + k)，但是线段树的常数k比树状数组要大。也就是说树状数组性能要稍微优于线段树。

而且树状数组的代码量和代码逻辑相对线段树要清晰和简洁。

凡是可以用树状数组解决的问题，用线段树也可以，反之不然。

针对不同的题目，我们有不同的方案可以选择（假设我们有一个数组）：

数组不变，求区间和：「前缀和」、「树状数组」、「线段树」 多次修改某个数（单点），求区间和：「树状数组」、「线段树」 多次修改某个区间，输出最终结果：「差分」 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小） 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）

1. 简单求区间和，用「前缀和」
2. 多次将某个区间变成同一个数，用「线段树」
3. 其他情况，用「树状数组」