lucifer

前面我们讲了线段树以及线段树是如何高效解决某些区间问题的。不少人也听说过树状数组，据说树状数组也可以解决一些区间问题。那么树状数组和线段树有什么区别呢？它们又有什么联系呢？本文将带你一探究竟。

背景

给一个两个数组，其中一个数组是 A [1,2,3,4]，另外一个数组是 B [5,6,7,8]。让你求两个数组合并后的大数组的：

• 最大值
• 最小值
• 总和

这题是不是很简单？我们直接可以很轻松地在 $O(m+n)$ 的时间解决，其中 m 和 n 分别为数组 A 和 B 的大小。

那如果我可以修改 A 和 B 的某些值，并且我要求很多次最大值，最小值和总和呢？

朴素的思路是原地修改数组，然后 $O(m+n)$ 的时间重新计算。显然这并没有利用之前计算好的结果，效率是不高的。 那有没有效率更高的做法？

有！线段树就可以解决。

​