1 树状数组能解决什么问题？#

先看例题 P3374 【模板】树状数组 1 。对于一个数列，我们需要支持以下两个操作：

1. 将某一个数加上 $x$ ；
2. 求出某区间每一个数的和。

对于这道题，如果用普通的方法暴力枚举，我们可能只会拿到70%的分数。然而如果利用树状数组，我们就能获得满分。可见：树状数组能够支持动态修改并查询前缀和，从而求出某区间的和。

2 树状数组的结构是怎样的？#

我们直接来5个点（点中的数字是编号，不是值）。

接下来，让我们建立一棵树。

以每两个节点作为叶子结点向上建立二叉树。

每一个橙色的节点就表示其所有字树的和。下面让我们为橙色节点也标上编号。特别地，对于节点1, 3 和 5，我们把它标记为特殊的橙色节点（原因以及标法下面会讲）。节点编号用二进制表示。

我们先约定，对于原数组，我们用数组 $a$ 来储存；而橙色节点的数组我们用 $bit$ 来储存（注意，有些并不是所有橙色节点都有编号。对于没有编号的橙色节点，我们就不用管它了）。

下面我们列出一些等式关系：

• $bit[001] = a[001]$
• $bit[010] = a[001] + a[010]$
• $bit[011] = a[011]$
• $bit[100] = a[001] + a[010] + a[011] + a[100]$
• $bit[101] = a[001] + a[010] + a[011] + a[100] + a[101]$

很难发现规律？我们换个角度看。

• 对于 $a[001]$，它被包含在 $bit[010], bit[100]$ 中；
• 对于 $a[010]$，它被包含在 $bit[010], bit[100]$ 中；
• 对于 $a[011]$，它被包含在 $bit[100]$ 中；
• 对于 $a[101]$，它被包含在 $bit[101]$ 中。

如果把树画得大一点，可能会更容易地发现规律。而规律就是：对于任意一个 $a[x]$，每次取 $x$ 的最低位并加上 $x$，就能一步一步地找到它所有的父亲。

是不是很神奇？我们拿 $a[001]$ 来举个例子，加深理解。

1. 首先，$a[001]$ 的第一个父亲为 $001$ 本身，是 $bit[001]$；
2. 取到 $001$ 的最低位的值 $001$，$001 + 001 = 010$，那么$bit[010]$ 就是它的第二个父亲。
3. 再然后，$010 + 010 = 100$，则 $bit[100]$ 就是第三个父亲。

3 用代码实现单点修改#

了解了基本的树状数组的构造方式，让我们来实现原数组的单点修改。

我们知道，$bit$ 数组存的是它下面所有孩子的和；相反地，若要修改一个 $a$ 的值，就要修改它每一个父亲的值。而这就要用到上一章节中提到的如何遍历每一个父亲的方法。

1
int lowbit(int x){
2
  return x & -x;
3
}

1
void change(int x, int y){
2
  while(x <= n){
3
    bit[x] += y;
4
    x += lowbit(x);
5
  }
6
}

4 查询区间和#

现在，给出任意的两个端点 $[ l , r ]$，要求出 $a[ l ] + ... + a[ r ]$，应该怎么做呢？

回想普通前缀和的做法，我们只要求出 $pre[ r ] - pre[ l - 1 ]$ 即可。类似地，我们要利用树状数组求出区间和，就要写一个 query （查询）函数，来求出 $a[1] + ... + a[n]$ 的值，相当于普通前缀和中 pre 的功效，从而就能轻松求出某一区间的和了。

1
int query(int x){
2
  int res = 0;
3
  while(x){
4
    res += bit[x];
5
    x -= lowbit(x);
6
  }
7
  return res;
8
}

1
query(r) - query(l - 1)

5 示例代码#

1
#include<cstdio>
2
#include<iostream>
3
using namespace std;
4
const int maxn=5e5+10;
5
int n,m;
6
int a[maxn];
7
int bit[maxn];
8
int k,x,y;
9
int lowbit(int x){
10
    return x & -x;
11
}
12
void change(int x,int y){
13
    while(x<=n){
14
        bit[x]+=y;
15
        x+=lowbit(x);
16
    }
17
}
18
int query(int x){
19
    int ans=0;
20
    while(x>0){//边界条件x>0!
21
        ans+=bit[x];
22
        x-=lowbit(x);
23
    }
24
    return ans;
25
}
26
int main(){
27
    cin>>n>>m;
28
    for(int i=1;i<=n;i++){
29
        scanf("%d",&a[i]);
30
        change(i,a[i]);//一开始都是0，要初始化加上a[i]
31
    }
32
    for(int i=1;i<=m;i++){
33
        scanf("%d%d%d",&k,&x,&y);
34
        if(k==1){
35
            change(x,y);//将第x个数加上y
36
        }else{
37
            printf("%d\n",query(y)-query(x-1));//求出区间和
38
        }
39
    }
40
    return 0;
41
}

注意：请使用较快的输入输出，否则可能会超时。

6 FAQ#

1. 为什么数组名称要叫做 bit ？ 答：因为树状数组的英文全称叫做 Binary Indexed Tree，简称 BIT。
2. 树状数组的时间复杂度是多少？ 答：虽然树状数组和线段树的理论时间复杂度都是 $O(log_2 n)$，但是树状数组代码简单，实际时间复杂度会略低一些。
3. 为什么能想到树状数组这样的数据结构？ 答：天才发明的，天知道。