数据结构: 树状数组

概述

• 树状数组(Binary Indexed Tree，BIT，或称Fenwick Tree)支持区间查询、单点修改 一个区间的总信息由区间内所有元素共同贡献而得 然而一般的树状数组具有限制(与前缀和数组类似，因为朴素树状数组查询取件信息依赖于前缀和)：
  • 元素间运算满足结合律
  • 所有元素具有逆元，即满足消去律(可由运算结果及其中一个操作数得知另一个操作数)
  • 满足上述要求的区间信息包括加和、乘积、异或等
• 一些特殊类型的树状数组可实现一些不满足上述要求的区间查询问题：
  • 双树状数组求区间最值
  • 扩展树状数组求不满足消去律的运算的区间信息
• 树状数组可求解的问题是线段树的子集，在后面可见其结构并非一棵完美的二叉树 但其价值在于能以更简单的代码、更小的空间/时间常数因子来完成相似任务

基本结构

• 为了实现最基本的树状数组的功能，需要考虑(接下来以求区间和为例)：

  • 数组的每个元素代表哪一个区间的区间信息(称为基本区间)
  • 如何通过基本区间信息，来求任意范围的区间信息
  • 修改单点值时，如何更新所有涉及该点的元素

• 设数组索引为$i$($1\le i\le n$)，$g(i)$为$i$二进制最右边第一个$1$的位置($g(i)\ge 0$) 则$a_i$管辖的范围为$[i-2^{g(i)}+1,\ i]$ 例如，$a_1$管辖$[1,1]$、$a_2$管辖$[1,2]$、$a_4$管辖$[1,4]$、$a_6$管辖$[5,6]$ 考虑$2^{g(i)}$的具体实现：实际就是$i-(i\&(i-1))=i\&(-i)$

• 区间查询：获取任意范围的区间信息便很简单，由于前缀区间信息非常易于获取、且运算满足消去律 因此若设$h(x,y)$为区间$[x,y]$的区间信息，则$h(x,y)=h(1,y)-h(1,x-1)$，其中-为该运算的逆运算 获取前缀区间信息的方式：令$i$迭代为$i-2^{g(i)}$直到$i=0$退出循环、将途径的基本区间信息$a_i$求和即可，是$O(\log n)$的

• 单点修改：

  • 先考虑其树形态，即不同元素区间之间的包含关系，可以发现： 若有$x<y<x+2^{g(x)}$，则$a_y:[y-2^{g(y)}+1,y]$、$a_x:[x-2^{g(x)}+1,x]$ 由于$y-2^{g(y)}+1>x$，故此时$a_y、a_x$管辖区间互不包含 且$a_x$区间真包含于$a_{x+2^{g(x)}}$区间 其树形结构便是：对于一个结点$y$，其直接子结点$x$必须满足$x+2^{g(x)}=y$ 对任意$x<y<x+2^{g(x)}$，$x、y$所在结点的最近共同祖宗不是$x$或$y$
  • 因此单点修改的过程类似获取前缀区间信息的逆过程：令$i$迭代为$i+2^{g(i)}$直到$i>n$退出循环、使途径的基本区间信息$a_i\leftarrow a_i+new-old$ 因此也是$O(\log n)$的

• 建树：

  • $O(n\log n)$：变为$n$次单点修改，其中$new=r_i、old=0$
  • $O(n)$：在$O(n\log n)$的方法中，每次从叶子结点(原数组元素)上升到根结点，多花了$\log n$； 由于该树中，父结点的编号一定比所有直接子结点的编号大 因此除了方法一$c_i=\sum a_k[i-2^{g(i)}+1\le k\le i]$，还可$c_i=\sum a_k[k+2^{g(k)}=i]$ 因此在从小到大更新结点时，可顺便更新其直接父结点：$a_i\leftarrow a_i+r_i、a_{i+2^{g(i)}}\leftarrow a_{i+2^{g(i)}}+a_i$
  • $O(n)$：在输入时不进行建树，而是计算前缀和，输入完成后进行区间查询来建树 因此空间、时间复杂度的常数因子比方法二略大

• 原数组的区间修改与单点查询：差分运算也可使用树状数组，因为差分数组的前缀和即为原数组元素，对于这个问题，只需要多一步计算差分数组的步骤 即，如果要求是原数组的区间修改+单点查询，可转化为原数组的差分数组的：两点修改+求出区间和，这个要求和之前的分析一致 因为区间$[x,y]$修改后，差分数组只有$a_x、a_{y+1}$需要修改 此时使用方法二建树时，由于只使用一个数组，因此需记录$a_{i-1}$来计算$a_i$的值(令$a_0=0$) 时间复杂度：仅在预处理时多了一遍$O(n)$，各种操作的复杂度均不变

• 原数组的区间修改与区间查询：沿用上述方法，用差分数组来实现$O(\log n)$的区间修改，对于区间查询，通过两个前缀和相减得到 可以对式子展开：如果原数组为$a$，差分数组为$b$，那么

  $$\begin{align}s_k=\sum_{i=1}^ka_i=\sum_{i=1}^k\sum_{j=1}^ib_j=\sum_{i=1}^k(k-i+1)b_i=k\sum_{i=1}^kb_i-\sum_{i=1}^k(i-1)b_i\end{align}$$

  即，维护两个树状数组，一个是其差分数组，另一个是带$i-1$系数的差分数组(更新时乘上系数即可) 计算原数组的前缀和$s_k$时，使第一个树状数组的前缀和乘$k$再减去第二个树状数组的前缀和即可 时间复杂度：各种操作的复杂度的常数因子增大

• 朴素树状数组模板：

  c++

  #define lbit(x) (x & (-x))
  int a[100001], n, i, t;
  int query(int x) { // 查询前缀和
   int ans = 0;
      while (x) {
          ans += a[x];
          x -= lbit(x);
      }
      return ans;
  }
  int query(int x, int y) { // O(log n) 区间查询
      return query(y) - query(x - 1);
  }
  void set_a(int idx, int val) { // O(log n) 单点修改
      val = val - a[idx];
      while (idx <= n) {
          a[idx] += val;
          idx += lbit(idx);
      }
  }
  int main() {
      cin >> n;
      // 使用方法二建树
      for (i = 1; i <= n; ++i) {
          cin >> t;
          a[i] += t;
          if ((t = i + lbit(i)) <= n) {
           a[t] += a[i];
          }
      }
  }

扩展树状数组

BIT应用

统计逆序对问题

• 即冒泡排序的最小交换次数[ NOIP 2013 提高组] 火柴排队

区间最值问题

区间与区间求和问题