基础知识：树状数组

没错，是我。练习时长两年半的个人练习生又出来丢人了==

呜呼！一直以来都以为树状数组就是二叉树的数组表示，然后做题的时候感觉越来越不对劲——我印象里树状数组可没有这么多方便的性质和功能啊？这题目怎么就树状数组呢？但是因为懒惰就一直得过且过，尽可能忽略的都忽略了……直到矛盾爆发的今天：我读了一个自称树状数组的题目，结果发现我并不能读得懂它的代码== 才发觉大事不妙，该学了（）

不知道树状数组这个东西在我的那些纸质书籍里有没有记载，现在这篇文章就是基于网上可以查到的公开资料整理写成的。如果之后看了书有新的收获再在这里补充就好了。

本文出现的图片大多来自互联网。

定义

首先先看一下来自百度百科的树状数组的定义：

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为 $log(n)$ 的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在 $log(n)$ 的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

特点

复杂度：查询和修改的时间复杂度都是 $log(n)$ ，空间复杂度则为 $O(n)$ 。
用途：通常用来高效的计算数列的前缀和，区间和，和线段树有点像。
可解决的问题：可以解决大部分基于区间上的更新以及求和问题。
缺陷：比起线段树来说，在遇到复杂的区间问题还是不能解决。所以说该上线段树还是得上==
解题时，应当优先考虑使用树状数组，再考虑使用线段树。

渐近式理解

关于二叉树、线段树和树形数组的理解大概可以简单归纳成这样：

二叉树	线段树	树状数组
就是二叉树啊，一个爸爸两个儿子，儿子可能还有儿子，这样形成的一个结构啊。	如果每个爸爸都存两个儿子的值，就可以方便一些区间问题的解决了。	比起线段树又删去了一部分节点，这样子就可以使用数组建树了。

图示

然后我就在网上找了个树状数组的图，它长这样：

这里的A数组就是原来的数组，C数组就是利用这个数组构建的树状数组。可以看出A数组和C数组的节点数是一样的。但是和原数组不同的是，树状数组的每个节点存储的是在这个意义上它的子节点的值和。也就是：

\begin{aligned} C_1\ &=\ A_1 \\ C_2\ &=\ A_1 + A_2 \\ C_3\ &=\ A_3 \\ C_4\ &=\ A_1 + A_2 + A_3 + A_4 \\ C_5\ &=\ A_5 \\ C_6\ &=\ A_5 + A_6 \\ C_7\ &=\ A_7 \\ C_8\ &=\ A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 \\ C_9\ &=\ A_9 \end{aligned}

可以发现C数组的取值是有规律的： $C_i=A_{i-2^k+1}+A_{i-2^k+2}+\cdots+A_i$ 。这里公式里的k就是i的二进制中从最低位到高位连续零的长度。

光是这么说还是比较的混乱，那么我们先引入lowbit的概念：

lowbit：数字二进制表示的最低1所在位的值。
它的实现是#define lowbit(x) (x&-x)，返回数字x的二进制表示的最低位的二进制1所在的位置所代表的值。
特别地，有lowbit(0) = 0。这样的时候可能会死循环，所以写成函数再加上一个判断会好一些。事实上0就是边界。

lowbit返回的值只有一个二进制数字位是1，所以显然它是2的幂。这真的是一个非常巧妙的实现。我是不知道先辈是怎么想出来的，但是又过于理所应当所以不详细解释了。

~~天呐之前写lowbit竟然还是循环加移位，太蠢了我死了~~

~~如果不知道原码补码反码我就说一下~~

整数的最高位是符号位，0是正数，1是负数；其他的是数字位。
正整数的原码，反码和补码都是这个数字的二进制表示。
负整数的原码的数字位和相对应的正整数是一样的，只是符号位是1；它的反码就是数字位全部取反，补码就是反码加上二进制1.

这样，我们就知道刚才的公式里的k其实是满足这样的关系的： $lowbit(x) = 2^k$ 。那么也就是说上面的公式说明了：C数组的每个节点（假设位置i）的值等于从A数组上它的位置开始向前数lowbit(i)个节点的值的和。这也就是树状数组的性质： $C_i = \sum_{j=i+1-lowbit(i)}^{i} A_j$ ，已经知道了lowbit(i)是位置i的最大的是2的幂的因子。

构建树状数组

从上面的基本定义已经可以了解到C数组的指定位置的值的求法。C数组的节点可能包含多个A数组节点的值，相应地A数组的一个节点可能会被多个C数组的节点包含。在这个基础上就可以介绍对树状数组的一些操作了：

节点修改

因为A数组的节点可能被多个C数组的节点包含，所以更新的时候要把这些都考虑到。因为 $C_i = \sum_{j=i+1-lowbit(i)}^{i} A_j$ ，所以 $A_k$ 会被 $C_j \mid j \in \lbrace k\leq J_i\leq N \mid J_1 = k, J_i = J_{i-1} + lowbit(J_{i-1}) \rbrace$ 更新A节点的代码大概长这样：

void add(int i, int x)
{
    if (i < 1) return;    // 在数组外
    while (i <= N)        // N 指数组长度
    {
        C[i] += x;
        i += lowbit(i);   // 向上找爹爹
    }
}

这样，就可以在已知A数组的情况下构建出树状数组C了，大概这么做：

void build()      // 一般不写成函数
{
    for (int i=1;i<=N;++i)
        add(i,A[i]);
}

因为是无后效的在线算法，所以可以一边输入一边构建。事实上一般解题过程中就是这么做的。

节点查询

因为并不是每个节点都包含了在自己前面所有节点的值，所以当需要查询前缀和的时候，仍然需要向前推进。下面的query(int):int函数返回的是原数组在区间[1,p]上的前缀和。

int query(int p)
{
    int res = 0;
    while (p > 0)
    {
        res += C[p];
        p -= lowbit(p);
    }
    return res;
}

/* 或者也可以写成这个样子 */
int query(int p)
{
    int res = 0;
    for (int i=p;i;i-=i&-i)
        res += C[p];
    return res;
}

既然可以求出前缀和，那么也可以简单的利用前缀和求出区间的和：

int query(int l, int r)
{
    return query(r)-query(l-1);
}

以上就是单点更新的树状数组的两项基本操作了。但是当题目要求更新区间内的所有值时，它的优势就不那么明显了。

树状数组的变式

上面说到的树状数组是最普通的单点更新的树状数组，它可以在 $O(log(n))$ 的时间内更新单个节点的值，或者计算出区间和。但是如果数组的更新形式不是单点更新而是区间更新，这样的树状数组就没那么好用了，需要进行一些变换才好。

~~毕竟，高级树状数组即使是在很大的范围也可以进行局部优化降低复杂度的……我不会就是了~~

区间修改+节点查询

这里的修改区间指的是将原数组的某个区间内的每个值都增加x。这样的操作如果是在单点更新的树状数组中，就只能遍历更新区间内的每一个值，复杂度达到 $O(nlog(n))$ ，这是不好的。

一种改进的方法就是不再根据数据的值建树，转而引入差分，利用差分建树。

~~那么差分是什么呢，赶紧百度百科一下~~

差分：又名差分函数或差分运算，差分的结果反映了离散量之间的一种变化，是研究离散数学的一种工具。它将原函数 $f(x)$ 映射到 $f(x+a)-f(x+b)$ 。差分对应离散，微分对应连续。差分又分为前向差分、向后差分及中心差分三种。
差分算子：设y依赖于自变量t，当t变化量为1时因变量y的改变量记为 $Dy_1$ ，称为函数 $y(t)$ 在点t处步长为1的(一阶)差分。
所谓前向/后向/中心差分就是这个变化量的方向不同。对原序列进行差分计算可以得到长度相等（或长度大一）的差分序列。它有着这样的性质：
对差分序列求前缀和可以降低差分序列的阶数，最终得到原序列。
原序列[L,R]区间内值+x等价于差分序列中，L处+x，R+1处-x。

在了解差分的基础上，我们规定A₀=0，前向差分序列为数组D。也就是说 $D_j=A_j-A_{j-1}$ 。根据上面说到的性质，我们可以得到以下的关系：

查询： $A_i = \sum_{j=1}^i D_j$
修改： $A_{L\to R}+x \Leftrightarrow D_L+x,D_{R+1}-x$

这样的差分序列有一个巨大的优势：修改一个区间就仅需要修改区间的上下界的两个值。所以为了加速区间的修改，我们可以利用这个性质对D数组建立树状数组，就可以方便区间修改了。

综上所述，如果要进行修改和查询，可以写出这样的代码：

void add(int p, int x)
{
    while(p <= N)
    {
        D[p] += x;
        p += p&-p;
    }
}

void add(int l, int r, int x)
{
    add(l,x);
    if (r<N) add(r+1,x);  // 可以不判断
}

int ask(int i)            // 差分前缀和，即A[i]
{
    int res = 0;
    while (i)
    {
        res += D[i];
        i -= i&-i;
    }
    return res;
}

因为这里的树状数组D是根据原数组A的一阶差分序列而构建的，所以构建时的输入应该是A数组两个元素的差：

void build()      // 依然是在线算法
{
    for (int i=1;i<=N;++i)
        add(i,A[i]-A[i-1]);
}

这样，更新的过程被大大的简化，依然可以在 $O(log(n))$ 的复杂度完成区间的更新和单点查询。但是这也导致了这样的树状数组不能快速的查询区间内值的和。

区间修改+区间查询

如果问题模型既有大量的区间修改又有大量的区间查询怎么办？这样的情况似乎即使是上面的那种树状数组也不是很够用。在开始之前我们先考虑上面说的差分数组，显然有：

\sum_{i=1}^nA_i=\sum_{i=1}^n\sum_{j=1}^iD_j

也就是说：

\begin{aligned} \sum_{i=1}^nA_i&=\sum_{i=1}^n (n+1-i)D_i\\ &=n\sum_{i=1}^nD_i-\sum_{i=1}^n(i-1)D_i \end{aligned}

只要知道了 $\sum_{i=1}^nD_i$ 和 $\sum_{i=1}^n(i-1)D_i$ ，就可以求出A数组的前缀和。而这两个表达式本身都是前缀和。前缀和可以通过维护树状数组方便的求出。所以这次需要分别对D数组和与D数组相关的乘积进行树状数组维护。

因为两个数组都是和D数组相关，可以整到一起一并处理。设乘积的树状数组是sum数组，那代码大概就可以写成下面这样：

void add(int p, int x)  // 传入A的差分序列
{
    int k = p-1;
    while (p <= N)
    {
        D[p] += x;
        sum[p] += k*x;
        p += p&-p;
    }
}

void query(int p)       // 查询A数组的前缀和
{
    int res = 0, k = p;
    while (p)
    {
        res += k*D[p]-sum[p];
        p -= p&-p;
    }
    return res;
}

void ask(int i)         // 查询A数组节点
{
    int res = 0;
    while (i)
    {
        res += D[i];
        i -= i&-i;
    }
    return res;
}

void add(int l, int r, int x)
{
    add(l,x);
    add(r+1,x);         // 做题时数组开大点
}

void query(int l, int r)
{
    return query(r)-query(l-1);
}

这样的树状数组就既可以满足区间修改的需要，也可以快速的进行区间查询和节点查询了。大多数的问题都可以使用这样的树状数组来解决吧。

对比线段树

最开始的时候就提到了。树状数组思想上继承自线段树，两者极为相似，但是树状数组的空间复杂度比线段树要小，并且实现更加的简单容易。但是作为代价，它的使用范围比线段树是要小的。

树状数组的优劣

树状数组的优势：空间复杂度略低，编程复杂度低，容易扩展到多维情况。
比线段树的劣势：适用范围小，对可以进行的运算也有限制。

~~等我知道了再完善这一部分~~

实现的对比

这里为了对线段树和全功能一维树状数组的实现进行对比，先简单的介绍以下线段树的几大基本操作的实现：

操作	线段树实现描述	树状数组实现描述
构造	使用递归，每次递归二分，直到区间[l,r]缩为一个点。	在线构建
单点修改	向下找到包含的节点，并全部修改	使用`lowbit`找爸爸，修改所有包含。
单点查询	自上而下一直搜索到目标节点，将路径上的节点值求和即可	传统树状数组可直接查询，或求差分序列的前缀和
区间查询	在每一个节点（区间），若完全包含就加上，否则递归不完全的区间。	使用`lowbit`向前直到完成计算前缀和，之后使用前缀和计算区间和
区间修改	和查询类似，完全包含的区间就直接加上，否则就递归直到找到完全包含。	如果是差分序列的树状数组，就仅需对区间两端进行修改就可以满足。

上述线段树基本操作的实现如下，一般来说用来表示线段树的数组的大小是原数组的四倍。

/* 定义线段树节点结构体 */
struct node 
{
    int l,r,v;    // 区间和数值
    bool ispoint(){return l==r;}
} t[4*N];         // 线段树数组

/* 构建线段树： 从根[1~n]开始 */
void build(int l, int r, int i)
{
    t[i].l = l;
    t[i].r = r;
    if (l==r) return;
    int m = (l+r)>>1;
    build(l,m,i<<1);
    build(m+1,r,(i<<1)^1);
}

/* 线段树单点修改： A[p]+=k */
void add(int i, int p, int k)
{
    t[i].v += k;
    if (t[i].ispoint()) return;
    if (p <= t[i<<1].r)
        add(i<<1,p,k);
    else if (p >= t[(i<<1)^1].l)
        add((i<<1)^1,p,k);
}

/* 线段树区间查询： ΣA[l~r]的值 */
int query(int i, int l, int r)
{
    if (t[i].l >= l && t[i].r <= r)
        return t[i].v;
    int res = 0;
    if (l <= t[i<<1].r)
        res += query(i<<1,l,r);
    if (r >= t[(i<<1)^1].l)
        res += query((i<<1)^1,l,r);
    return res;
}

/* 线段树区间修改： A[l~r]+=k */
void add(int i, int l, int r, int k)
{
    if (t[i].l >= l && t[i].r <= r)
    {
        t[i].v += k;
        return;
    }
    if (l <= t[i<<1].r)
        add(i<<1,l,r,k);
    if (r >= t[(i<<1)^1].l)
        add((i<<1)^1,l,r,k);
}

/* 线段树单点查询： A[p]的值 */
int ask(int i, int p)
{
    int res = t[i].v;
    if (t[i].ispoint()) return res;
    if (p <= t[i<<1].r)
        res += ask(i<<1,p);
    else if (p >= t[(i<<1)^1].l)
        res += ask((i<<1)^1,p);
    return res;
}

这里的实现只是最基础的线段树实现，并没有引入延迟标记之类的优化。如果要使用线段树还应该使用别的板子。

总结

简单的一维树状数组大概就是上面说到的三种。它们的特点简单整理为下表：

类型	简介	树状数组	ask	query	add
单点修改	传统的树状数组，可以快速求出前缀和区间和	基于A维护C	直接返回A[i]	返回A的前缀和	更新指定节点
区间修改	可以快速的修改区间的值，但不支持快速求出原数组的前缀和	基于A的差分维护D	返回A的差分的前缀和	-	更新区间首尾节点
区间查询	既可以快速修改区间，也可以快速区间查询	基于A的差分维护D，以及一个乘积的sum	返回A的差分的前缀和	根据推导公式返回	更新区间首尾节点

二维树状数组

在和线段树做对比的时候提到了树状数组更容易扩展到多维情况，那这里就简单地提一下多维情况下的树状数组。此时，它的复杂度是 $O(log^kn)$ 。

练习题

这里列了几个网上看到的出现的比较多的板子题。等我写完了就会把代码放上来的。

洛谷 P3374

题目链接：https://www.luogu.com.cn/problem/P3374

洛谷 P3368

题目链接：https://www.luogu.com.cn/problem/P3368

template <class T>
class tree_array
{
    vector<T> c, d;

    static uint lowbit(uint x)
    {return x & -x;}

    void add(uint i, T x)
    {
        uint ii = i, siz = c.size();
        while (ii < siz)
        {
            c[ii] += x, d[ii] += x * i;
            ii += lowbit(ii);
        }
    }

    T sum(uint i)
    {
        T ret = 0; uint ii = i;
        while (ii)
        {
            ret += (i + 1) * c[ii] - d[ii];
            ii -= lowbit(ii);
        }
        return ret;
    }

public:
    tree_array() = default;
    explicit tree_array(uint n) : c(n + 1), d(n + 1) {}
    void resize(uint n) {c.resize(n + 1), d.resize(n + 1);}

    void add(uint l, uint r, T x)
    {add(l, x); add(r + 1, -x);}

    T ask(uint l, uint r)
    {return sum(r) - sum(l - 1);}
};

signed main()
{
    int n, m, x; cin >> n >> m;
    tree_array<longs> a(n + 1);
    for (int i = 1; i <= n; ++ i)
    {cin >> x; a.add(i, i, x);}
    while (m --)
    {
        int op, y, k;
        cin >> op >> x;
        if (op == 1)
        {
            cin >> y >> k;
            a.add(x, y, k);
        }
        else cout << a.ask(x, x) << endl;
    }
    return 0;
}

UPD: 2021-3-26 已验证板子的正确性；

洛谷 P3431

题目链接：https://www.luogu.com.cn/problem/P3431

HDU - 1166

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
外挂链接：https://vjudge.net/problem/HDU-1166