树状数组

树状数组

树状数组（Binary Indexed Tree，BIT）是一种用于维护动态集合和查询的数组结构。它支持动态集合的插入、删除、查询操作，时间复杂度为O(logn)。

BIT的基本思想是利用树状数组来维护一个序列的前缀和，并通过树状数组的查询操作来实现动态集合的插入、删除、查询操作。

BIT的实现可以分为两步：

1. 计算前缀和：将序列中的元素逐个累加，并存储在树状数组中。

2. 维护前缀和：对树状数组进行维护，使得树状数组中的元素表示该序列的前缀和。

BIT的查询操作可以在O(logn)的时间内完成，具体过程如下：

1. 计算查询位置的前缀和：通过树状数组的查询操作，计算查询位置的前缀和。

2. 计算查询范围的前缀和：通过树状数组的查询操作，计算查询范围的前缀和。

3. 计算查询结果：通过前缀和的差值，计算查询结果。

管辖区间

树状数组中，规定 c[x] 管辖的区间长度为 2^{k}，其中：

• 设二进制最低位为第 0 位，则 k 恰好为 x 二进制表示中，最低位的 1 所在的二进制位数；
• 2^k（c[x] 的管辖区间长度）恰好为 x 二进制表示中，最低位的 1 以及后面所有 0 组成的数。
  举个例子，c_{88} 管辖的是哪个区间？

因为 88_{(10)}=01011000_{(2)}，其二进制最低位的 1 以及后面的 0 组成的二进制是 1000，即 8，所以 c_{88} 管辖 8 个 a 数组中的元素。

因此，c_{88} 代表 a[81 \ldots 88] 的区间信息。

我们记 x 二进制最低位 1 以及后面的 0 组成的数为 \operatorname{lowbit}(x)，那么 c[x] 管辖的区间就是 [x-\operatorname{lowbit}(x)+1, x]。

这里注意：\boldsymbol{\operatorname{lowbit}} 指的不是最低位 1 所在的位数 \boldsymbol{k}，而是这个 1 和后面所有 0 组成的 \boldsymbol{2^k}。

怎么计算 lowbit？根据位运算知识，可以得到 lowbit(x) = x & -x。

区间查询

查询 a[1 \ldots 7] 的过程：

从 c_{7} 往前跳，发现 c_{7} 只管辖 a_{7} 这个元素；然后找 c_{6}，发现 c_{6} 管辖的是 a[5 \ldots 6]，然后跳到 c_{4}，发现 c_{4} 管辖的是 a[1 \ldots 4] 这些元素，然后再试图跳到 c_0，但事实上 c_0 不存在，不跳了。

我们刚刚找到的 c 是 c_7, c_6, c_4，事实上这就是 a[1 \ldots 7] 拆分出的三个小区间，合并一下，答案是 c_7 + c_6 + c_4。

观察上面的过程，每次往前跳，一定是跳到现区间的左端点的左一位，作为新区间的右端点，这样才能将前缀不重不漏地拆分。比如现在 c_6 管的是 a[5 \ldots 6]，下一次就跳到 5 - 1 = 4，即访问 c_4。

我们可以写出查询 a[1 \ldots x] 的过程：

• 从 c[x] 开始往前跳，有 c[x] 管辖 a[x-\operatorname{lowbit}(x)+1 \ldots x]；
• 令 x \gets x - \operatorname{lowbit}(x)，如果 x = 0 说明已经跳到尽头了，终止循环；否则回到第一步。
• 将跳到的 c 合并。
  实现时，我们不一定要先把 c 都跳出来然后一起合并，可以边跳边合并。

比如我们要维护的信息是和，直接令初始 ans = 0，然后每跳到一个 c[x] 就 ans <-ans} + c[x]，最终 \mathrm{ans} 就是所有合并的结果。

int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}