区间 Range

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

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

「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？

答案：并不是，而且恰好相反，只有在我们遇到第 4 类问题，不得不写「线段树」的时候，我们才考虑线段树。因为「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。

总结一下，我们应该按这样的优先级进行考虑：

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

时间复杂度：add 操作和 query 的复杂度都是 O(log⁡n)，因此构建数组的复杂度为 O(nlog⁡n)。整体复杂度为 O(nlog⁡n)
空间复杂度：O(n)

逆序数是一个数列中在它前面有比它大的个数。如4312的逆序数是0+1+2+2=5。
从最后一个数开始遍历，每次在树状数组中查询有多少个数小于当前的数并加入计数器，之后把当前元素加入树状数组。

树状数组

正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。

更新

但是，如果还可以修改数组中的元素呢？
比如我把下标为1的元素修改了，由于所有前缀都包含下标1，那么就需要更新所有前缀的元素和，更新操作就需要O(n)的时间，这太慢了。
能不能把前缀[1,i]拆分成若干段连续子数组呢？
如果拆分得太细，比如拆分成[1,1]，[2,2]，[3,3]，虽然更新是O(1)的，但计算子数组元素和还是得遍历累加，时间复杂度是O(n),太慢了。

平衡

上面的做法，要么询问是O(1)更新是O()，要么询问是O(n)更新是O(1),时间差距悬殊。
如何「平衡」询问和更新的时间复杂度？
关键在于如何拆分子数组（区间）。
能否把任意前缀拆分成若干个关键区间，使得更新操作也只会更新若干个关键区间？
这样回答询问时，只需要遍历并累加若干个关键区间的元素和。更新元素时，也只需要遍历并更新若干个关键区间的元素和。

如何拆分？

启示：如果把一个正整数i拆分成若干个不同的2的幂（从大到小），那么只会拆分出O(logi)个数。前缀能否也这样拆分呢？
举个例子，13=8+4+1，那么前缀[1,13]可以拆分成三个长度分别为8,4,1的关键区间：
[1,8], [9,12], [13,13]。
按照这个规则，来看看从[1,1]到[1,8]是如何拆分的：

树状数组总是结合离散化

• 逆序对
• 区间和的个数

线段树