树状数组学习笔记

发表于 | 更新于 | 分类于 ，
本文字数： 4.2k

先来看一道题。

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某一个数加上x
  2. 求出某区间每一个数的和
输入输出格式
输入格式:

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式:

输出包含若干行整数，即为所有操作2的结果。

输入输出样例
输入样例#1:
1
2
3
4
5
6
7
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出样例#1:
1
2
14
16
说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

原题链接: https://www.luogu.org/problemnew/show/P3374

分析

这题我们如果用朴素的做法,则每次修改的复杂度为$O(1)$,每次查询的复杂度为$O(n)$,对于这题的数据规模难以承受。所以我们需要一种更为高效的数据结构,这里讲两个相对简单的,也就是树状数组和线段树。(写完树状数组感觉没时间再写了,所以线段树留到过两天再写)

对于这两种操作,树状数组和线段树的复杂度都是$O(logn)的。$

树状数组

基本思想

我们把整个区间分为若干个小区间,定义$C[i]$为区间第i个元素所维护的区间信息(比如在本题中,它所维护的区间信息就是这段小区间中所有数字的和)。

那么每个元素所维护的区间的具体范围是什么呢?先来看看这张图:

图片纯手绘。我们可以看到,$C[1]$维护的是[1, 1]的区间信息,而$C[2]$维护的是[1, 2]的区间信息,$C[3]$维护的是[3, 3]的区间信息,其他元素所维护的区间在图中也都能看出来。那么我们来找一下规律:

  • 1转为二进制是0000 0001,它维护了大小为1的区间
  • 2转为二进制是0000 0010,它维护了大小为2的区间
  • 3转为二进制是0000 0011,它维护了大小为1的区间
  • 4转为二进制是0000 0100,它维护了大小为4的区间
  • 5转为二进制是0000 0101,它维护了大小为1的区间
  • 6转为二进制是0000 0110,它维护了大小为2的区间
  • 7转为二进制是0000 0111,它维护了大小为1的区间
  • 8转为二进制是0000 1000,它维护了大小为8的区间

(这里的区间大小的意思是区间最右元素序号-区间最左元素序号+1)
有什么规律呢?规律就是:第$i$个元素序号转为二进制后,每位上要么是0要么是1,那么我们把位数最低的1所在的位数设为$x$,则这个元素就维护了大小为$2^x$的区间信息,记为$lowbit(i)$。可以证明,$lowbit(i) = i \& (-i)$。

结论就是: 第$i$个元素维护了大小为$lowbit(i)$的区间的信息。

单点修改,区间查询

回到刚才放的那张图,我们定义原序列的第$i$个元素为A[i],现在想要让A[1]+=1,那么C中的元素又该怎么变化呢?

由于$C[1]$维护的就是$A[1]~A[1]$的信息,因此$C[1]$一定也是要+=1的。$C[2]$维护的是$A[1]~A[2]$的信息,这段区间的信息也有了变化,所以$C[2]$也要+=1。可以发现,如果$C[i]$有变化,则$C[i+lowbit(i)]$也要有变化。那么我们就可以写出以下代码:

1
2
3
4
5
6
7
int c[500001], n;    //n为整个序列包含的元素数量
int lowbit(int x) {
    return x & (-x);
}
void add(int x, int v) {     //将序列中第x个数+=v
    for(; x <= n; x += lowbit(x))  c[x] += v;
}

修改完了元素,我们要查询某段区间中元素的和。如果我们想要查询区间[a, b]的和,我们只需要查询出[1, a]的和以及[1, b]的和,再用sum([1, b]) - sum([1, a]),就得到了[a, b]的和。

设[1, x]的和为$ans$,那么ans一定要+=c[x],也就是[x - lowbit(x) + 1, x]的区间和。从1到$x$有若干个小区间,我们加上[x - lowbit(x) + 1, x]的区间和后,让x-=lowbit(x),则问题就变为求[1, x - lowbit(x)]的区间和。对于这个问题我们仍可以用同样的方法解决它，最后就得到了[1, x]的区间和。代码如下:

1
2
3
4
5
int query(int x) {   //查询[1, x]的区间和
    int ans = 0;
    for(; x >= 1; x -= lowbit(x))  ans += c[x];
    return ans;
}

当我们要查询[a, b]的区间和时,我们只需要写query(b) - query(a - 1)就可以了。

那么下面放上文章开头问题的AC代码:

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
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

int n, m, c[500100];

int lowbit(int x) {
    return x & (-x);
}

void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

int sum(int x) {
    int ans = 0;
    while (x >= 1) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        add(i, x);
    }
    for (int i = 0; i < m; i++) {
        int a, x, y;
        scanf("%d%d%d", &a, &x, &y);
        if (a == 1)  add(x, y);
        if (a == 2)  printf("%d\n", sum(y) - sum(x - 1));
    }
    return 0;
}

区间修改,单点查询

对应的也有一道题。

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数数加上x
  2. 求出某一个数的值
输入输出格式
输入格式:

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x 含义：输出第x个数的值

输出格式:

输出包含若干行整数，即为所有操作2的结果。

输入输出样例
输入样例#1:
1
2
3
4
5
6
7
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出样例#1:
1
2
6
10
说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

原题链接: https://www.luogu.org/problemnew/show/P3368

分析

这道题很多人用差分来做,其实还有另一种更简单的方法,就是把修改和查询操作反过来。

当我们修改某个区间的值时,我们采用刚才的区间查询的迭代方式,把遍历到的每个元素加上这个值,就像打上了标记一样。查询时,采用刚才的单点修改的迭代方式,返回的是遍历到的元素的和。具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, c[500100];

int lowbit(int x) {
    return x & (-x);
}

void add(int x, int k) {
    for (; x >= 1; x -= lowbit(x))  c[x] += k;
}

int query(int x) {
    int ans = 0;
    for (; x <= n; x += lowbit(x))  ans += c[x];
    return ans;
}

区间修改,区间查询

没想到还有这种黑科技,然而我不会,以后填坑。