前言：在这个毒瘤算法上，比起证明，我更喜欢背模板。Awa

树状数组

  • 树状数组是一个查询和修改复杂度都为 log2nlog_2n 的数据结构。主要用于：单点修改，区间求和。
  • 树状数组的管理区间：
    • tr[i]:i−lowbit(i)+1∼itr[i]: i-lowbit(i)+1\sim i
  • tr[i]tr[i] 的特点：
    • a·除根外，结点 xx 的父结点 =x+lowbit(x)=x+lowbit(x)
    • b.除根外，结点 xx 的前一个“结点” $ =x - lowbit(x)$
    • c.树的深度 =log2n=log_2n

单点修改

  • 在 aa 数组下标为 xx 的位置 +v+v
1
2
3
void update(int x,int v){
	for(int i = x;i <= n;i += lowbit(i)) tr[i] += v;
}

前缀和

  • trtr 求 [1,x][1,x] 所有数的和
1
2
3
4
int query(int x) {
	int res = 0;
	for (int i = x; i > 0; i = i - lowbit(i)) res += tr[i];
}

T1

  • 板子题。水题一道。
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
#include <bits/stdc++.h>
using namespace std;
int n, a[1010101];
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) a[i] += u;
}
int query(int x) {
	int res = 0;
	for (int i = x; i > 0; i -= lowbit(i)) res += a[i];
	return res;
}
int main() {
	int m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d",&x);
		update(i, x);
	}
	while (m--) {
		int k, x, y;
		scanf("%d%d%d",&k,&x,&y);
		if (k == 0) {
			printf("%d\n", query(y) - query(x - 1));
		}else{
			update(x,y);
		}
	}
}

T2 【一本通提高篇树状数组】 数星星

  • 根据输入已经帮我们排好第一关键字的情况下，直接跑树状数组版本的单调栈板子
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
#include <bits/stdc++.h>
using namespace std;

int a[1510101];
int tr[1501010], n;
int lowbit(int x) {
	return x & -x;
}
void update(int x, int u) {
	for (int i = x; i <= 32010; i += lowbit(i)) tr[i] += u;//x的上界不是n！
}
int query(int l) {
	int res = 0;
	for (int i = l; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int x, y;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d",&x,&y); //树状数组必须从1开始！所以y+1！
		printf("%d\n",query(x + 1)); //这里星星本身并不算在内，所以要先进行查询，然后再update
		update(x + 1, 1);
	}
}

T3【一本通提高篇树状数组】 校门外的树【数据加强强强版】

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
/*
首先这个题你已经知道是个树状数组了，而且强制在线。然后呢，如果在种树的时候一个一个update的话就很浪费对吧，而且会T
那我们仅记录种树的L，R，如果当前我询问的区间的R大于这个种树的L而且这个L>=询问的L，那就代表我当前询问的区间内包含（不一定完全包含）该种树的区间。
那就代表这个种树区间一定是答案的一种，然后我们统计有多少个这样的区间即可。
先算有多少个区间的L小于当前我种树的R，然后算出来的数再减去有多少个区间的L小于询问的L即可。
*/
#include <bits/stdc++.h>
using namespace std;
int n, k, x, y, tl[101010], tr[101010], m;
int lowbit(int x) {
	return x & -x;
}
void updatel(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tl[i] += u;
}
void updater(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int queryl(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tl[i];
	return res;
}
int queryr(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d",&k,&x,&y);
		if (k == 1) {
			updatel(x, 1);
			updater(y, 1);
		} else {
			cout << queryl(y)/*查左端点小于y*/ - queryr(x - 1)/*查右端点小于x，因为右端点等于x也算在区间内，所以要减1*/ << "\n";
		}
	}
}

【一本通提高篇树状数组】清点人数

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
/*
阅读理解+水题一道
首先校长在m节车厢就是查询1-m的总人数
有人上下车就是update，下车就是update一个负数
几节车厢就是几个值来建树状数组
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, tr[10101000];
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		char op[2];
		int l, r;
		scanf("%s%d", &op, &l);//可恶只能输入字符数组
		if (op[0] == 'A') {
			printf("%d\n", query(l));
		} else if (op[0] == 'B') {
			scanf("%d", &r);
			update(l, r);
		} else {
			scanf("%d", &r);
			update(l, -r);
		}
	}
}

P3368 【模板】树状数组 2

image

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
/*
有点难度，需要差分，首先我们需要注意到为什么它不问区间求和而是单点查询？有猫腻
我们构造差分数组，再在差分数组的基础上构造树状数组，那么我们先把原数组做差分，
这时，查询点x的值就是把1-x的值都加起来，不就是query(x)吗？
对于区间加减操作，我们就采用差分的区间操作的方法，把tr[l]++,tr[r+1]--，就完结了~
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, k, op, tr[1010101];
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) {
		tr[i] += u;
	}
}
int query(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int a[1010100], d[1010100];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		d[i] = a[i] - (i == 1 ? 0 : a[i - 1]);
		update(i, d[i]);
	}
	for (int i = 1; i <= m; i++) {
		cin >> op;
		if (op == 1) {
			cin >> x >> y >> k;  
			update(x, k);
			update(y + 1, -k);
		} else {
			cin >> x; 
			cout << query(x) << '\n';
		}
	}
	return 0;
}

D. 计算能力

  • 纯板子
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
/*
这题水的很。用树状数组做相当于用坦克打鸟了。。。
这题前缀和直接解决，因为它是离线的。
我们这里用树状数组做（毕竟是树状数组专题）
*/
#include <bits/stdc++.h>
using namespace std;

int tr[101010], n, m, l, r;

int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int u) {
	int res = 0;
	for (int i = u; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &l);
		update(i, l);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &l, &r);
		printf("%d\n", query(r) - query(l - 1));
	}
}

E. 小X算排名

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
/*
这不纯唐吗？！就离谱
树状数组记录有多少点在他前面（表示在数轴上）记得+1，因为处理分数为0的时候会死循环
*/
#include <bits/stdc++.h>
using namespace std;
int n,m;
int tr[101101],a[101010];
int lowbit(int x){
	return x & -x;
}
void update(int p,int u){
	for(int i = p;i <= 100010/*这里不是n！！！特别注意！！*/;i += lowbit(i)) tr[i] += u;
}
int query(int u){
	int res = 0;
	for(int i = u;i > 0;i -= lowbit(i)) res += tr[i];
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a[i]);
		update(a[i]+1,1);//必须+1！！！分数中有零！lowbit(0)=0! 会死循环、、、
	}
	for(int i = 1;i <= n;i++){
		printf("%d\n",n-query(a[i]+1)+1);//这里需要仔细推一下
	}
	
	
}

F. 不稳定的数字

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
思路有些难，但是水
我们需要找满足两个条件的数来判断当前数是否符合条件：
(1)大于当前数 (2)都在当前数的左边/右边
我们设当前判断的数是 X
那么，我们把所有数表示在数轴（桶）上，然后跑树状数组 query(X)的到的就是小于等于X的数的数量
然后直接n-query(X)就是大于X的数的数量
如何求X左边/右边大于X的数的数量呢？
假设我们现在要查X左边的数，那我们肯定不想让X右面的数进入答案
直接不计算那些数不就行了吗？我们在计算每个X的时候，从前到后先让X进入数轴，然后再跑n-query(x)
然后再让下一个X进入数轴，以此类推，就能够求出每个X的对应值了，
该方案的正确性在于X右面（后面）的数还未进入数轴，但是X前方的数已经进入了数轴，
所以不会计算X右面的数，自然也不会把X右面大于X的数计算在内了~
X右面也一样，倒叙求X即可。
但是————注意数据范围！还要离散化~
*/
#include <bits/stdc++.h>
using namespace std;

int tr[101010], a[101010], b[101010], n, k;
int ls[101010], rs[101010]; //左面&右面每个X的结果
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int u) {
	int res = 0;
	for (int i = u; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	n = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++) {

		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
//		cout << a[i] << " ";
		update(a[i], 1);
		ls[i] = query(n) - query(a[i]); //这里必须用query(n)
		
	}
//	cout << endl;
	memset(tr, 0, sizeof tr);
	for (int i = n; i >= 1; i--) {
		update(a[i], 1);
		rs[i] = query(n) - query(a[i]); //这里必须用query(n)
	}
	for (int i = 1; i <= n; i++) {
//		cout << ls[i] << " " << rs[i] << endl;
		if (ls[i] > rs[i]) {
			if (rs[i] * 2 < ls[i]) k++;
		} else {
			if (ls[i] * 2 < rs[i]) k++;
		}
	}
	cout << k << endl;
}

【一本通提高篇树状数组】简单题

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
/*
很简单的区间修改，单点查询的恶心树状数组题。
我们构造差分数组，然后在差分数组的基础上构建树状数组，这样，单点查询就只需要修改L和R+1下标的点了，区间修改O(logn)
因为是单点查询，根据差分数组的特性可知，一个点的数值在差分数组中表示为1-这个数的和，正好对应树状数组query(这个数)
完结撒花~
*/
#include <bits/stdc++.h>
using namespace std;

int n, a[1010101], tr[1010101], m;

int lb(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lb(i)) tr[i] += u;
}
int query(int u) {
	int res = 0;
	for (int i = u; i > 0; i -= lb(i)) res += tr[i];
	return res;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int k, l;
		scanf("%d%d",&k,&l);
		if (k == 2) {
			printf("%d\n", query(l) % 2);
		} else {
			int r;
			scanf("%d",&r);
			update(l, 1);
			update(r + 1, -1);
		}
	}
}

【一本通提高篇树状数组】清点人数

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
/*
阅读理解+水题一道
首先校长在m节车厢就是查询1-m的总人数
有人上下车就是update，下车就是update一个负数
几节车厢就是几个值来建树状数组
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, tr[10101000];
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		char op[2];
		int l, r;
		scanf("%s%d", &op, &l);//可恶只能输入字符数组
		if (op[0] == 'A') {
			printf("%d\n", query(l));
		} else if (op[0] == 'B') {
			scanf("%d", &r);
			update(l, r);
		} else {
			scanf("%d", &r);
			update(l, -r);
		}
	}
}

H. 冒泡排序统计

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
/*
经典阅读理解。
首先，阅读理解就是一个冒泡排序的板子，什么意思呢？就是每次将一个字母从前往后移动直到它周围的数的大小关系合适。
我们先要明白一个事就是不能暴力。平方复杂度直接炸了
每当我们移动一个数到正确的位置，cnt就加一。
而对于每一个数a[i]而言，在a[i]前面而且比a[i]大的数一定要跑到a[i]后面才能有序。
每轮排序，每个数只会被他前面比他大的数交换一次，因此如果a[i]前面有X个比他大的数，那这二者就会交换X+1次（有一次用于验证数组是否有序）
那我们只需要统计有多少个数在他前面且比他大就行了，这部分的做法请看上一题的说明，最后选那个X最大的数+1作为答案。
*/
#include <bits/stdc++.h>
using namespace std;
int n, tr[1010101], ans, a[1010101], b[1010101];
int lb(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lb(i)) tr[i] += u;
}

int query(int u) {
	int rss = 0;
	for (int i = u; i > 0; i -= lb(i)) rss += tr[i];
	return rss;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	int k = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b;
		ans = max(query(k) - query(a[i]), ans);
		update(a[i], 1);
	}
	cout << ans + 1 << endl;
}

【一本通提高篇树状数组】打鼹鼠

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
/*
二维树状数组板子。强制在线
*/
#include <bits/stdc++.h>
using namespace std;

int tr[1050][1051], n, m, x, y, k;
int lb(int x) {
	return x & -x;
}
void update(int x, int y, int u) {
	for (int i = x; i <= n; i += lb(i)) {
		for (int j = y; j <= n; j += lb(j)) {
			tr[i][j] += u;
		}
	}
}
int query(int x, int y) {
	int res = 0;
	for (int i = x; i > 0; i -= lb(i)) {
		for (int j = y; j > 0; j -= lb(j)) {
			res += tr[i][j];
		}
	}
	return res;
}
int query_lr(int x, int y, int u, int v) {//特殊标注
	return query(u, v) - query(x - 1, v) - query(u, y - 1) + query(x - 1, y - 1);
}

int main() {
	cin >> n;
	for (int i = 1;; i++) {
		int u, v;
		scanf("%d", &k);
		if (k == 3) return 0;
		scanf("%d%d%d", &x, &y, &u);
		if (k == 1) {
			update(x + 1, y + 1, u);
		} else if (k == 2) {
			scanf("%d", &v);
			printf("%d\n", query_lr(x + 1, y + 1, u + 1, v + 1));
		} else return 0;
	}
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
首先我们看这个过程肯定是插入排序，但是暴力的复杂度高得离谱
那么，暴力的思想就是不断向后移动这个数字，直到他到达正确的位置。
那我们的优化就应该是把无聊的移动过程给去掉。
假设我们当前的状态是[1,3,2,4,5]
那么我们当前在最后的已经排好序的序列应该是[4,5] -> 有序区
那没排好序的就是[1,3,2] -> 无序区。
我们要一个一个的把无序区中的数移动到有序区的正确位置，就能够构成完整的序列，移动次数就是最终答案。
那么，假设我们现在要移动X到有序区，我们必须保证移动后X在整个有序区中的相对位置是正确的，
那X前面的数必须小于X，X后面的数必须大于X。
我们把有序区的数全放到下标标记数组里（数轴上），
这样跑一遍query(X)就能知道有多少个数比X小，自然知道X插入在哪一个位置能够符合上述条件了。
比X小的数有query(X)个，那么X需要先移动到无序区的最后一位，移动次数就是无序区数字数量减一，
然后移动到最终的正确位置的次数是query(X)，将这二者加起来就是最终结果。
移动成功后只需要在数轴上（标记数组中）标记X的值以便下一个数query。具体语句：a[X]++;
对所有无序区的数进行该操作，最终的操作数加起来就是结果了。
时间复杂度：O(nlogn)
完结撒花~
*/
#include <bits/stdc++.h>
using namespace std;
int tr[1010110], n, a[1010101], op[1010101], start = 1, endd;
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int p) {
	int res = 0;
	for (int i = p; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	start = n, endd = n;
	for (int i = n - 1; i >= 1; i--) {
		if (a[i + 1] - a[i] > 0) start--;
		else break;
	}
	cout << start << " " << endd << "\n";
	for (int i = start; i <= endd; i++) {
		update(a[i], 1);
	}
	int k = n - (endd - start + 1);
	for (int i = 1; i < start; i++) {
		op[i] = k - 1 + query(a[i]);
		update(a[i], 1);
		k--;
	}
	cout << n - (endd - start + 1) << endl;
	for (int i = 1; i < start; i++) printf("%d ", op[i]);
}

J. 恢复数列

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
/*
从后往前查找。
把标记数组里面1-n赋值为1. 每次查找有多少个数比这个数小直接query(这个数)-1即可。
我们从后往前遍历每一个数。每次二分一个值，要求这个值满足query(这个值)-1 == c[i] ，这个值就是a[i]。然后在下标标记数组将该值赋值为0，即：update(a[i],-1)
*/
#include <bits/stdc++.h>
using namespace std;

int tr[101010], n, a[101010], c[101010];
int lowbit(int x) {
	return x & -x;
}
void update(int p, int u) {
	for (int i = p; i <= n; i += lowbit(i)) tr[i] += u;
}
int query(int u) {
	int res = 0;
	for (int i = u; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, 1);
	}
	for (int i = n; i >= 1; i--) {
		int l = 1, r = n;
		while (l <= r) {
			int mid = l + r >> 1;
			if (query(mid)-1 >= a[i]) r = mid - 1;
			else l = mid + 1;
		}
		c[i] = l;
		update(l, -1);
	}
	for (int i = 1; i <= n; i++) cout << c[i] << "\n";
}