文章

树状数组自学笔记

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

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

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

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

2 树状数组的结构是怎样的?

我们直接来5个点(点中的数字是编号,不是值)。

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

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

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

我们先约定,对于原数组,我们用数组 $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$ 的值,就要修改它每一个父亲的值。而这就要用到上一章节中提到的如何遍历每一个父亲的方法。

3.1 怎样获得最小一位二进制的值?

先给出结论:x & - x。这需要用到反码补码的知识。

首先,$x$ 是一个二进制正整数。那么,$- x$ 的原码就是把最高位的0变成了1,其反码就是最高位的1不变,剩下的所有数位取反。$- x$ 的补码就是在反码的基础上加1。而 $x$ 的补码与原码相同。那么,两者取,最高位一个是1一个是0,变成了0;剩下的数位,假设 $x$ 的原码最低位是1,那么 $x$ 的补码最低位就是1,而 $- x$ 的补码的最低位是0+1=1,而其他数位都恰好相反,所以前面的全部是0,只有最低位为1。类似地,如果最低位不是1,那么负数的反码加上1后只有最低的那位会进位,使得只有这位和正数的补码与上后会变成1,其它都是0。

于是我们定义函数 lowbit

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

它的作用是返回最低位的1的值。

3.2 实现遍历所有父亲节点并加上一个值

  1. 首先,$a[x]$ 的第一个父亲节点就是 $bit[x]$,这就是起点。
  2. 然后,我们将 $x$ 每次加上 $lowbit(x)$ (注意:lowbit(x)中的x是不断更新的x,而不是最开始的不变的x)x += lowbit(x);
  3. 对于每一个访问到的节点,都加上一个值 $y$ bit[x] += y;
  4. 边界条件:当父亲节点编号 $x > n$ 时(节点最多n个),退出循环 while(x <= n)

于是得到函数 change

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

change函数能将所有包含 x 的父亲加上 y

OK,现在我们实现了第一个任务:动态修改区间和。下面我们要实现动态查询区间和。

4 查询区间和

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

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

4.1 实现 query 函数

之前我们说过,要修改单点的值,就要遍历所有父亲,用的方法是 x += lowbit(x);。那如果是获取 $a[1] + … + a[n]$ 的值,是否也能用类似的方法呢?让我们把之前的图搬出来再来找找规律。

假设我们现在要获取 $a[1] + a[2] + a[3]$ 的值。此时 $n = 011$ ,则 $n - lowbit(n) = 010$(既然修改时是加上lowbit,那么查询时就反一下,减去lowbit),恰好能得到 $a[1] + a[2]$ 的和。如此一来,我们就能求出 $1 ~ n$ 的区间和了。

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

注意边界条件:x应该大于0

4.2 求出区间和

之前说过,query 就相当于 pre,所以易得:

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

这就是区间 $[l , r]$ 的值了。

5 示例代码

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

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

6 FAQ

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

© Dignite. 保留部分权利。 由  提供CDN加速。

浙ICP备2023032699号 | 使用 Jekyll 主题 Chirpy