问题描述

动态前缀和维护问题。给定一个区间 $A[1..n]$, 对该区间进行如下两类操作

(前缀和查询)指定$1 \le j \le n$, 求$A[1..j]$的前缀和
(单点修改)指定$1 \le j \le n$, 令A[j] += val

分析。该问题可以通过前缀数组$arr[1..n]$完成，空间复杂度是$O(n)$, 操作一的时间复杂度是$O(1)$, 操作二的时间是$O(n)$, 最坏情况是$j = n$时整个$arr[1..n]$均需要更新。树状数组能够把操作一和操作二的时间复杂度都降至$O(\log n)$, 空间是$O(n)$.

树状数组

树状数组是一类巧妙利用了二进制的数据结构. 在动态前缀和维护问题中，输入$1 \le j \le n$, 若我们能从二进制的观点来看待$j$, 则$j$至多有$\log n$位. 举例, 易知

$$j = 13_{10} = 1101_{2} = 8 + 4 + 1$$

从而求数组的$A$的前13项之和可以分成三步:

$$A[1..13] = A[1..8] + A[9..12] + A[13]$$

注意区间$A[1..8], A[9..12], A[13]$的区间大小分别就是8, 4, 1, 这对应了13的进制分解. 我们记

$$c[8] = A[1..8], c[12] = A[9..12], c[13] = A[13]$$

则若我们知道了数组$c[1..n]$, 则前缀和可以在$O(\log n)$时间内完成. 数组$c[1..n]$被称为树状数组.

树状数组的含义

在此之前, 首先我们来明确一下$c[j]$的含义，他是指以$A[j]$结尾的往前一段区间的和, 为了方便我们称这一段区间为$c[j]$的前缀区间. $c[j]$的前缀区间有多长？如下:

$$\left| c[j] \right| = j\ &\ (-j) $$

其中符号$&$表示按位与. 上式的实际意义是指$j$的二进制表示中最右边的1所占的权重. 举例，如$12_{10} = 1100_{2} = 8 + 4, 4 = 12\ & \ (-12)$, 则$c[12]$的前缀区间长度是4, 同理$\left | c[13] \right | = 1, \left | c[8] \right | = 8, \left | c[2] \right | = 2$. 可以看出规律，凡是$j$是2的幂次形式是$c[j]$的前缀区间长度总是j, 这是因为此时j仅有一个1.

前缀和查询

首先来考察操作一:前缀和查询操作. 给定$1 \le j \le n$, 怎样使用$c[1..n]$计算得到$A[1..n]$? 仍然以$j = 13$举例,

$$ \begin{aligned} A[1..13] & = A[1..8] & + A[9..12] & + A[13] \ & = c[8] + & c[12] & + c[13] \end{aligned} $$

我们知道

$$ \begin{aligned} 13 & = 1101 + 0 = & 13\ & = 1100 + 1 = & 12 + 1\ & = 1000 + 101 = & 8 + (4 + 1) \ & = 0000 + 1101 = & 0 + 13 \end{aligned} $$

从而我们可以通过反复抹除13的最右边的1来得到不同的$c[k]$, 将这些$c[k]$求和就是$A[1..j]$的值, 这样的$c[k]$总量不超过$\log n$, 从而我们可以在$O(\log n)$时间内完成前缀和查询. 不断抹除最右边的1可以通过j -= (j & -j)实现, 当然，边界条件是j > 0.

前缀和查询的完整代码

/// x = 1, 2, ..., n
int sum(int x) {
    int ret = 0;
    while (x > 0) {
        ret += c[x];
        x -= (x & -x);
    }
    return ret;
}

作为特例，对于数组$A[1..n]$的单点查询可以通过 $sum(j) - sum(j - 1)$得到$A[j]$. 查询$A$的子区间和$[lo, hi]$可以通过$sum(hi) - sum(lo - 1)$实现. 时间均是 $2 \times O(\log n)$, 渐进阶是$O(\log n)$

单点修改

给定$1 \le j \le n$, 置 $A[j] += val$, 显然要修改$c[1..n]$中的某些值以达到动态维护区间的目的。显然$A[j]$变了, $c[j]$一定变，此外，其他所有覆盖了$A[j]$的$c[k]$均需改变，如何找到这些$c[k]$? 更直接一点，如何找了这些$k$?

首先，显然这些$k \ge j$. 首先来考察一个实例$j = 3 = 0011$, 容易知道$c[3]$的前缀区间长度是1, 那么只比$j = 3$大一点点的又恰能覆盖$A[3]$的$k = ?$

我们首先取出3最右边的1，其权值恰好是$w = 1$, 我们令$4 = 3 + w = 0100$, 其值恰好是$c[4]$, 容易知道$c[4]$是第一个覆盖了$A[3]$的元素，然后下一个$k$怎么求？显然$8 = 0100 + 0100 = 4 + 4$, 我们将4的最右边的1取出，其权值$w = 4$, $c[8]$是覆盖了$c[4]$的一个元素.

从而，我们知道k值得计算是通过j += (j & -j)实现的，边界是j <= n. 再举一个实例，修改$A[13]$，对应应修改的$c[k]$是$c[13], c[14]$. 容易知道这些$c[k]$总量同样不会超过$\log n$个, 从而单点修改可以在$O(\log n)$时间内完成. 单点修改完整代码如下

void add(int j, int val) {
    while (j <= n) {
        C[j] += val; 
        j += (j & -j);
    }
}

构建树状数组

有了前两步的操作，构建一个树状数组十分直接

init(int* A, int n) {
    N = n + 1;
    for (int i = 0; i < N; ++i) c[i] = 0;
    for (int i = 1 /*注意*/; i < N; ++i) update(i, A[i - 1]);
}

总结

树状数组$C[1,\cdots,n]$是原数组$A[1,\cdots,n]$的预处理数组，其中包含了原始数组的所有信息。其主要是二进制的思想，即

1.sum(i). 为查询$A[1,\cdots,i]$之和，将$i$转化为二进制数，这样在不超过$\log i$次操作就能将前n个数之和统计出来。其具体实现只需一路沿i -= lowbit(i)计算sum +=C[i]即可,其中$i \gt 0$. 该算法时间是$O(\log n)$

2.add(i,val).进行$A[i] += val$, 同样将$i$视为二进制数，这样在不超过$\log i$次操作就能实现元素的add操作.其具体实现只需一路沿i += lowbit(i)修改C[i]+=val即可. 其中$i \le n$. 该算法时间是$O(\log n)$

树状数组的初始化就是首先令$C[1..n]=0$, 然后依次调用add(i, A[i]), i =1,2,...,n.

将下标看做二进制数，正是树状数组（Binary Indexed Tree）名字的由来，其中Binary指的是二进制而不是二叉。

还有一个需要注意的是，树状数组中的$C[i] = Sum(A[i-lowbit(i)+1,\cdots, i])$, 大白话就是$C[i]$是原数组$A$中以$A[i]$结尾（包含）的前$lowbit(i)$个元素之和

树状数组的优势具有以下优势

实现简单
时间常数小
开了一倍空间（zkw树动态维护前缀和需要两倍空间）

问题描述#

树状数组#

树状数组的含义#

前缀和查询#

单点修改#

构建树状数组#

总结#