动态区间求和——树状数组的基本应用

• 前言
• 问题引入
• 思路一览
• 具体分析

前言

准确来说，不应该叫做动态区间求和问题，只能说树状数组经常用于求和操作而已，但是正常的动态条件查询树状数组也是可以做的，具体的下面再说吧

问题引入

给出一个数组a[]，要求做两种操作，一种是修改数组中的一个数，一种是实现查询区间[lt, rt](lt <= rt <= n)的区间和

思路一览

1. BF做法：每次修改，然后遍历求和，每次遍历求和是O(n)，询问m次，时间复杂度就是O(mn)
2. BF做法：好吧，其实还是BF做法，但是和上面的又有一点不同，我们想起前缀和这个东西好像查询区间和问题的时间复杂度是O(1)的，但是新的问题来了，那就是每次修改之后都要更新前缀和数组，因此时间复杂度和上面是一样的，还是属于暴力的做法，前缀和大抵还是适合静态问题
3. 树状数组：根据二进制的特性记录数组的部分和（但凡扯到二进制好像都是(log n)），不得不说，二进制这玩意真惹人稀罕，树状数组的查询和修改都是经典的log n，加上查询次数，所以最后就是nlog n

具体分析

树状数组该从哪里开始具体分析，emmm，这个还真不知道，没啥顺序，随便扯扯，记录一下，先贴一张某乎大图
+

• 树状数组的记录
  上面说的是树状数组记录了数组的某些部分，这还真不是瞎说，我感觉其实树状数组的记录其实挺没规律的(lowbit部分暂时不提)，你看一会c[1]是a[1]，一会c[2]是a[1]+a[2]，等会c[3]有事a[3]了，这不是闹着玩嘛，确实，反正除了对着书看了之后能看明白一点，实在是看不大懂。这张图还很不错，下面的数组索引给的是二进制表示，这时候琢磨一会又有点眉目，c[1]和c[3]从低位向高位走遇到的第一个1组成就是1，所以只包含一个数，c[2]的最低位1及以后就是10，转化过来就是2，因此有两个数组成，c[8]同理，所以这里我们就大致可以记住一个结论，树状数组c[i]记录的是从第i位向前i的二进制最低位1个数的和，用公式表示就是c[i] = a[i-lowbit(i)+1] + a[i-lowbit(i)+2] + ... + a[i](好吧，不会用公式，心累)，当然，dls的???1000 = ???0001 —— ???0111我觉着也很nice
• lowbit()函数
  既然上面说完了树状数组的记录，那么问题来了，如何求出那个最低位的1，这个时候就要用到计算机底层的应用了，计算机在内存中存储十进制数一般是以二进制形式，二进制形式加法是ok的，但是减法是存在问题的，那么之后是怎么解决的呢，答案是依靠溢出，这个大家就自己去了解吧，总而言之，二进制的存储形式分为原码、反码、补码，-x相当于将x的每一位按位取反再加1，可以大致让x=???100，那么先按位取反，得到???011，此时问号未知部分是相反的，这个时候加1，那么后部分的会变得相同且没有进位，即-x=!? !? !? 100，此时按位与就可以得到最低位的1

  lowbit(int x) {return x&-x;}
  

• 修改与查询
  这个我感觉也说不明白原理性的玩意，只能说修改自底向上，查询自顶向下，自增自减换位低位的进位退位

  void modify(int i, int x) {
      for(; i <= n; i += lowbit(i)) c[i] += x;
  }
  int query(int x) {
      int res = 0;
      //i一定不要为0，不然会死循环
      for(; i; i -= lowbit(i)) res += c[i];
      return res;
  }
  

• 细节碎碎念
  • 可以不用原数组，直接使用树状数组，单点查询可以使用a[i] = c[i] - c[i-1]得到，不过这样的单点查询时间复杂度就高了
  • 查询是查询1-n的前缀和，区间和可以使用前缀和相减得到
  • 树状数组的最初功能是单点修改，区间查询，由此基础上可以扩展区间修改，单点查询(将维护的数组从原数组变成差分数组，差分数组的前缀和就是原数组的值)，以及区间修改，区间查询，维护两个树状数组，主要就是推公式得来
  • 差分好像很合适树状数组，一是可以把区间修改换为单点修改，二是它的前缀和和原数组有关
  • 树状数组的经典应用就在于数学公式的推导，要求出一个查询结果和前缀和相关的公式
  • 树状数组关于区间最值的查询，其实区间求和可以做，那么区间求最值肯定也是可以的，不过这样的话就要辅助的原数组了，这里我的评价是贴出杭电1754，以及Code