「数据结构详解·十五」树状数组

「数据结构详解·一」树的初步
「数据结构详解·二」二叉树的初步
「数据结构详解·三」栈
「数据结构详解·四」队列
「数据结构详解·五」链表
「数据结构详解·六」哈希表
「数据结构详解·七」并查集的初步
「数据结构详解·八」带权并查集 & 扩展域并查集
「数据结构详解·九」图的初步
「数据结构详解·十」双端队列 & 单调队列的初步
「数据结构详解·十一」单调栈
「数据结构详解·十二」有向无环图 & 拓扑排序
「数据结构详解·十三」优先队列 & 二叉堆的初步
「数据结构详解·十四」对顶堆
「数据结构详解·十五」树状数组

0. 前置知识：lowbit 运算

我们定义 $\text{lowbit}(x)$ 为 $x$ 在二进制下最低的 $1$ 所代表的数。
如 $\text{lowbit}(1010_2)=10_2=2_{10},\text{lowbit}(11101_2)=1_2=1_{10}$ 。

我们要如何计算这个东西呢？
一种通常的计算方法是 $\text{lowbit}(x)=x\&((\sim x)+1)=x\&-x$ ，手模一下可以得到正确性。

现在你学会了计算 lowbit，下面就可以学习树状数组了！

1. 树状数组的概念

树状数组(Binary Indexed Tree, BIT, Fenwick Tree)，也称作二叉索引树，是一种维护序列信息的数据结构。所维护的序列信息和运算需要满足一定的要求：

可差分性：即如果知道了 $a\circ b$ 和 $a$ ，可以推得 $b$ 。
结合律：即维护的信息所做的运算 $\circ$ 满足 $(a\circ b)\circ c=a\circ(b\circ c)$ 。

在树状数组中，记 $\text{bit}_i$ 为区间 $\textbf{[\textit{i-}lowbit(\textit i)+1,\textit i]}$ 的信息和。
那么，对于一个序列 $a$ 的前缀信息，都被划分成了 $\textbf{log}$ 块。
如图所示，底部的点是 $a_i$ ，上方的点是 $\text{bit}_i$ 。

下面以例题具体解释树状数组的实现。

2. 例题详解

2-1. Luogu P3374 【模板】树状数组 1 / Loj 130 树状数组 1 ：单点修改，区间查询

思考一下我们修改位置 $x$ 的数会影响的到的 $\text{bit}_i$ 。
结合上图的观察，可以发现，如果我们从下往上修改，当修改的是 $x$ ，则下一次修改的就是 $x+\text{lowbit}(x)$ （具体证明留给读者思考）。

而查询 $\sum\limits_{i=l}^ra_i$ 可以拆成 $\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i$ 。
显然查询前缀和我们只要不断减去当前的 $\text{lowbit}$ 即可。

修改和查询的时间复杂度都是 $O(n\log n)$ 。
具体实现：

#include<bits/stdc++.h>
using namespace std;

struct fwk{
    int n,bit[500005];

    void init(int i)
    {
        n=i;
        memset(bit,0,sizeof(bit));
    }

    void add(int i,int c)
    {
        for(;i<=n;i+=i&-i) bit[i]+=c;
    }

    int qry(int i)
    {
        int res=0;
        for(;i;i-=i&-i) res+=bit[i];
        return res;
    }
}bit;

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	int n,m;
	cin>>n>>m;
    bit.init(n);
	for(int i=1;i<=n;i++)
	{
        int x;
		cin>>x;
		bit.add(i,x);
	}
	while(m--)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1) bit.add(x,y);
		else cout<<bit.qry(y)-bit.qry(x-1)<<endl;
	}
    return 0;
}

2-2. Luogu P3368 【模板】树状数组 2 / Loj 131 树状数组 2 ：区间修改，单点查询

我们 BIT 只能单点修改啊？怎么办！
其实，只要将序列 $a$ 差分成为 $b$ 后（ $b_i=a_i-a_{i-1}$ ），就变成了单点修改 $b_{l}\gets b_l+x,b_{r+1}\gets b_{r+1}-x$ ，区间查询 $\sum\limits_{i=1}^xb_i$ 了。
代码和上一题几乎是一样的，所以不再展示了。

2-3. Luogu P3372 【模板】线段树 1 / Loj 132 树状数组 3 ：区间修改，区间查询

这就不是很好做了。
首先区间查询就是 $\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i$ ，也就是说我们只要考虑如何求一个前缀和 $\sum\limits_{i=1}^xa_i$ 。
同上一题一样，将 $a$ 差分得到 $b$ ，有这样的推导：

秒客网