树形数据结构 -- 树状数组

写在前面的话

由于一些原因，我很久没有写CSDN文章了，写的不好请见谅

简介

树状数组，是一种STL主要支持如下两种操作：

1. 修改数组中的一个元素
2. 计算区间$[l,r]$的和

时间复杂度为$O(logn)$

基础款

让我们从一道例题开始:
题目传送门

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

• 将某一个数加上 x
• 求出某区间每一个数的和

由于$0\le n,m\le 100000$，所以暴力做法肯定行不通，需要使用树状数组。
让我们设原数组为$a$，树状数组为$b$，则：

• $b[1]$ = $a[1]$
• $b[2]$ = $a[1]+a[2]$
• $b[3]$ = $a[3]$
• $b[4]$ = $a[1]+a[2]+a[3]+a[4]$
• ……

总结规律：$b[i]=a[i-2$^k $+1]+a[i-2$^k $+2]+\dots \dots +a[i]$
其中，$k=lowbit(i)$

关于lowbit

lowbit即一个二进制数中从右往左数第一个1所表示的数
例如：
$x=10$，则，$x$的二进制为$1010$,那么，$lowbit(x)$即为$2$
C++代码实现：

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

或

#define lowbit(x) (x) & -(x)
1

如此操作后，我们便可以利用$b$数组在$O(logn)$的复杂度下求出任意一个$[1,x]$区间的和，或 将任意一个元素增加$k$

代码实现

update

void update(int i, int k) //把第i个数增加k
{
	for(; i <= n; i += lowbit(i)) b[i] += k; //b为树状数组
}
1
2
3
4

上述操作后，即可实现update功能

sum

int sum(int i) //求出1~i的区间和
{
	int ans = 0;
	for(; i; i -= lowbit(i)) ans += b[i];
	return ans;
}
1
2
3
4
5
6

在上述操作的基础上，利用前缀和的思想，即可求出任意区间$[l,r]$的区间和。
即：sum(r) - sum(l-1)

例题

到了这里，相信你已经一定程度上学会了树状数组，以下几道例题可供练手：
P3374 【模板】树状数组 1
P5057 [CQOI2006]简单题
P4939 Agent2

拓展1：树状数组求逆序对

让我们还是从一道例题开始：
P1908 逆序对

求出长度为$n$的数组$a$中所有逆序对
逆序对定义如下：

• 在数组$a$中，若满足$a[i]>a[j]$ 且 $i<j$，则$a[i]、a[j]$为逆序对

由于$0\le n\le 500000$，所以暴力做法肯定会$TLE$，那么，该怎么使用树状数组优化呢？
你猜

离散化

这里先卖个关子，简单讲一下离散化。
原理简述：

由于不是本文重点，直接上代码：

#include <algorithm>
#include <cstdio>
using namespace std;

typedef pair<int, int> PII;
PII ls[500010];
int a[500010];

bool cmp(PII x, PII y)
{
	if(x.first == y.first) return x.second < y.second;
	return x.first < y.first;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &ls[i].first);
		ls[i].second = i;
	}
	sort(ls+1, ls+n+1, cmp);
	for(int i = 1; i <= n; i++) a[ls[i].second] = i;
}
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

好，补充完离散化，接下来开始讲讲如何求逆序对
首先，先将数组$a$离散化，可以明确，离散化后，$a$将变为$1$ 到 $n$的一个排列。
接下来，维护树状数组$b$，具体操作如下：

1. 倒序遍历离散化数组$a$，依次update(a[i], 1)
2. 每次完成$update$后，ans += sum(a[i] - 1)
3. 遍历完成后，$ans$即为最终答案

可能有些难以理解。
首先，由于$a$是$1$到$n$的排列，所以$a$中$1$到$n$全部恰好出现一次，所以：

• sum(a[i]-1)即可理解为$1$到$a[i]-1$这个区间内已经加入到树状数组中的数字的个数。
• update(a[i], 1)可以理解为将$a[i]$标记为已经出现过

由于我们倒序遍历了$a$，所以每一次进行操作$2$时的sum(a[i] - 1)即可理解为：在数组$a$中，出现在$a[i]$之后的小于它的数字的个数；即以$a[i]$为第一个数的逆序对的个数

即可保证最终结果为$a$中所有逆序对的个数。

完整代码

#include <algorithm>
#include <cstdio>
#define lowbit(x) (x) & -(x)
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int n, tr[500010], a[500010];
PII ls[500010];
LL ans = 0;

void update(int i, int c)
{
	for(; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(int i)
{
	LL ans = 0;
	for(; i; i -= lowbit(i)) ans += tr[i];
	return ans;
}

bool cmp(PII x, PII y)
{
	if(x.first == y.first) return x.second < y.second;
	return x.first < y.first;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &ls[i].first);
		ls[i].second = i;
	}
	sort(ls+1, ls+n+1, cmp);
	for(int i = 1; i <= n; i++) a[ls[i].second] = i;
	for(int i = n; i >= 1; i--)
	{
		ans += sum(a[i]);
		update(a[i], 1);
	}
	printf("%lld", ans);
	return 0;
}
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
47
48

例题：

P1908 逆序对
P1774 最接近神的人
AcWing 241. 楼兰图腾

拓展2：树状数组+差分

让我们再次从一道例题开始：
P3368 【模板】树状数组 2

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

• 将某区间每一个数加上 x
• 求出某一个数的值

众所周知，树状数组支持 单点修改、区间求和，但是这题似乎反过来了：区间修改、求单点值。

区间修改……

有没有很熟悉？
这不是差分吗？！

差分怎么区间修改？比如将$[l,r]$内的全部值$+1$？
$b[l]+1$， $b[r+1]-1$

那么，差分如何求一个点的值呢？
累加。$b[1]+b[2]+\dots \dots +b[n]$ 换句话说：区间$[1,n]$的和 即是第$n$个数的值

emmmmmmmm……

豁然开朗有没有？单点修改，区间求和！树状数组出来了！
就是给树状数组里维护一个差分数组！

修改：

例如我们要把$[l,r]$ 加上 $k$：

update(l, k);
update(r+1, -k);
1
2

查询：

查询第$x$个数的值：

sum(x);
1

完事大吉！

上代码：

#include <algorithm>
#include <cstdio>
#define lowbit(x) (x) & -(x)
using namespace std;

int n, m, a[500010], ls[500010];

void update(int i, int k)
{
	for(; i <= n; i += lowbit(i)) a[i] += k;
}

int sum(int i)
{
	int ans = 0;
	for(; i; i -= lowbit(i)) ans += a[i];
	return ans;
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &ls[i]);
		update(i, ls[i] - ls[i-1]);
	}
	while(m--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int l, r, k;
			scanf("%d %d %d", &l, &r, &k);
			update(l, k);
			update(r+1, -k);
		}
		else
		{
			int t;
			scanf("%d", &t);
			printf("%d\n", sum(t));
		}
	}
	return 0;
}
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
47

尾声

快半年没更了，写的不好请在评论区喷射战士上线友善地提出
求三连QWQ