1. 数组不变，求区间和：前缀和、树状数组、线段树；
  2. 多次修改数组某单点值，求区间和：树状数组、线段树
  3. 多次修改某个区间，输出最终结果：差分
  4. 多次修改某个区间，求区间和：线段树、树状数组
  5. 多次将某个区间变为同一个树，求区间和：线段树、树状数组

总结：

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

    树状数组

    image.png
    所谓树状数组，就是用数组构成了树，方便我们进行区间求和。普通数组的单点修改时间复杂度为O(1)，区间求和的复杂度为O(n)；如果我们用前缀和维护数组的话，区间求和的复杂度将为O(1)，但单点修改会影响整个前缀和数组，复杂度为O(n)。我们是否能有这样一种数据结构，单点修改修改一小区间的和，区间求和利用多个小区间去求得。树状数组(BIT)是一种巧妙地利用了二进制的数据结构。
  • 单点修改：修改被管辖的范围的值，向上传递
  • 区间求和：通过管辖范围取得区间的和 ```go func (this *NumArray) add(index, val int) { for ; index < len(this.C); index += index & -index{
    1.   this.C[index] += val
    } }

func (this *NumArray) prefixSum(index int) (sum int){ for ; index >0; index -= index & -index{ sum += this.C[index] } return } ```