从零到树状数组&线段树

树状数组和线段树小结.

总想着总结下总咕咕了，

今天来填坑了， 总结下树状数组和线段树，

此文顺便全方面对比树状数组与线段树， 并加以题目验证

客观对比树状数组， 线段树 ( 再次体验树状数组的优雅

由于各种原因(懒)， 这里的从零开始指的是理解线段树和树状数组基础

持续跟新中...

单点修改， 区间求和

基础操作， 直接上例题吧

HDU - 1166

题意： 单点修改，区间求和

题解：树状数组优势项目， 主要代码就四五行，

树状数组就用lowbit进行区间跳跃， 进行修改和求和

这里用时间戳做了个小优化，达成清空数组的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct BitTree{
	int ans[Ma], b[Ma];
	void add(int pos, int val){
		for(; pos < Ma; pos += lowbit(pos))
			ans[pos] = b[pos] < T ? val : ans[pos] + val, b[pos] = T;
	}
    int sum(int pos){
		int s = 0;
		for(; pos; pos -= lowbit(pos))
			s += b[pos] < T ? 0 : ans[pos];
		return s;
	}
	int range(int l, int r){
		return sum(r) - sum(l - 1);
	}
};

线段树就用建树之后正常修改和查询即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct SegTree{
	int sum[Ma << 2];
	void build(int o, int l, int r){
		if(l == r){sum[o] = val[l];return ;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		sum[o] = sum[o << 1] + sum[o << 1 | 1];
	}
	void update(int o, int l, int r, int pos, int val){
		if(l == r){sum[o] += val;return ;}
		int mid = (l + r) >> 1;
		if(pos <= mid)update(o << 1, l, mid, pos, val);
		else update(o << 1 | 1, mid + 1, r, pos, val);
		sum[o] = sum[o << 1] + sum[o << 1 | 1];
	}
	int qSum(int o, int l, int r, int L, int R){
		if(l > R || r < L)return 0;
		if(l >= L && r <= R)return sum[o];
		int mid = (l + r) >> 1;
		return qSum(o << 1, l, mid, L, R) + qSum(o << 1 | 1, mid + 1, r, L, R);
	}
}

solution1:

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
/*********************************************************
Flie Name: hud1166.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年11月21日 星期四 15时40分28秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
#define lowbit(x) ((-x)&x)
#define Clear (++T)
using namespace std;

const int Ma = 5e4 + 100;

int T;

struct BitTree{
	int ans[Ma], b[Ma];
	void add(int pos, int val){
		for(; pos < Ma; pos += lowbit(pos))
			ans[pos] = b[pos] < T ? val : ans[pos] + val, b[pos] = T;
	}
    int sum(int pos){
		int s = 0;
		for(; pos; pos -= lowbit(pos))
			s += b[pos] < T ? 0 : ans[pos];
		return s;
	}
	int range(int l, int r){
		return sum(r) - sum(l - 1);
	}
}bt;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int To;
	cin >> To;
	for(int k = 1; k <= To; k++){
		cout << "Case " << k << ":\n";
		int n;
		cin >> n;
		for(int t, i = 1; i <= n; i++)
			cin >> t, bt.add(i, t);
		string com;
		while(cin >> com && com[0] != 'E'){
			int a, b;
			cin >> a >> b;
			if(com[0] == 'A')bt.add(a, b);
			else if(com[0] == 'S')bt.add(a, -b);
			else if(com[0] == 'Q')cout << bt.range(a, b) << '\n';
			else assert(false);
		}
		Clear;
	}
    
    return 0;
}

solution2:

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
65
66
67
/*********************************************************
Flie Name: hud1166.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年11月21日 星期四 15时40分28秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
#define lowbit(x) ((-x)&x)
#define Clear (++T)
using namespace std;

const int Ma = 5e4 + 100;

int val[Ma];

struct SegTree{
	int sum[Ma << 2];
	void build(int o, int l, int r){
		if(l == r){sum[o] = val[l];return ;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		sum[o] = sum[o << 1] + sum[o << 1 | 1];
	}
	void update(int o, int l, int r, int pos, int val){
		if(l == r){sum[o] += val;return ;}
		int mid = (l + r) >> 1;
		if(pos <= mid)update(o << 1, l, mid, pos, val);
		else update(o << 1 | 1, mid + 1, r, pos, val);
		sum[o] = sum[o << 1] + sum[o << 1 | 1];
	}
	int qSum(int o, int l, int r, int L, int R){
		if(l > R || r < L)return 0;
		if(l >= L && r <= R)return sum[o];
		int mid = (l + r) >> 1;
		return qSum(o << 1, l, mid, L, R) + qSum(o << 1 | 1, mid + 1, r, L, R);
	}
}st;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int To;
	cin >> To;
	for(int k = 1; k <= To; k++){
		cout << "Case " << k << ":\n";
		int n;
		cin >> n;
		for(int i = 0; i < n; i++)
			cin >> val[i];
		st.build(1, 0, n - 1);
		string com;
		while(cin >> com && com[0] != 'E'){
			int a, b;
			cin >> a >> b;
			if(com[0] == 'A')st.update(1, 0, n - 1, a - 1, b);
			else if(com[0] == 'S')st.update(1, 0, n - 1, a - 1, -b);
			else if(com[0] == 'Q')cout << st.qSum(1, 0, n - 1, a - 1, b - 1) << '\n';
			else assert(false);
		}
	}
    
    return 0;
}

单点修改， RMQ

线段树无脑项目，改改查询就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct SegTree{
	int Max[Ma << 2];
	void build(int o, int l, int r){
		if(l == r){Max[o] = val[l];return ;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
	}
	void update(int o, int l, int r, int pos, int val){
		if(l == r){Max[o] = val;return ;}
		int mid = (l + r) >> 1;
		if(pos <= mid)update(o << 1, l, mid, pos, val);
		else update(o << 1 | 1, mid + 1, r, pos, val);
		Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
	}
	int qMax(int o, int l, int r, int L, int R){
		if(l > R || r < L)return -inf;
		if(l >= L && r <= R)return Max[o];
		int mid = (l + r) >> 1;
		return max(qMax(o << 1, l, mid, L, R), qMax(o << 1 | 1, mid + 1, r, L, R));
	}
}st;

树状数组得来些优雅操作

直接搞？

1
2
3
4
void add(int pos, int val){
	for(; pos < Ma; pos += lowbit(pos))
		ans[pos] += val;
}

明显，初始构建时是可行的，但遇到后续修改的时候就出现问题了，每次都清空构建O(n * m * log(n))不现实

众所周知，lowbit保留了二进制下的最后一个一， 那么所能对当前数造成影响的所有数的下标是能通过加上那个一得到当前数下标的那些

也就是说 1001000, 能对他造成影响的只有

1000100 + lowbit(1000100) = 1000100 + 100 = 1001000

1000110 + lowbit(1000110) = 1000110 + 10 = 1001000

1000111 + lowbit(1000111) = 1000111 + 1 = 1001000

看到这儿， 你琢磨了一会， 发现， 不就是这样吗！

能影响当前数的不就是 \(x - 2^0, x - 2^1 ... x - 2^n\) (\(2^n < lowbit(x)\)) 吗？

于是一个O(log^2 n)的更新就诞生了

1
2
3
4
5
6
7
8
void add(int pos, int val){
	for(; pos < Max; pos += lowbit(pos)){
		ans[pos] = val;
		int t = lowbit(pos);
		for(int i = 1; i < t; i <<= 1)
			ans[pos] = max(ans[pos], ans[pos - i]);
	}
}

下面进行查询， 寻常树状数组的查询的东西都是带有可减性的，在这儿的最值可没有，

那么就从右边往坐跳， 如果跳了会出去，那么我就一个个看

1
2
3
4
5
6
7
8
9
void qMax(int l, int r){
	int qm = -inf;
	while(l <= r;){
		qm = max(qm, a[r]);
		r--;
		for(; r - lowbit(r) >= l; r -= lowbit(r))
			qm = max(qm, ans[r]);
	}
}

这样， 你就得到了一个O(log^2 n)的查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct BitTree{
	int ans[Ma];
	void change(int pos, int va){
		val[pos] = va;
		for(; pos < Ma; pos += lowbit(pos)){
			ans[pos] = val[pos];
			int t = lowbit(pos);
			for(int i = 1; i < t; i <<= 1)
				ans[pos] = max(ans[pos], ans[pos - i]);
		}
	}
    int Max(int l, int r){
		int s = -inf;
		while(l <= r){
			s = max(s, val[r]);
			r--;
			for(; r - lowbit(r) >= l; r -= lowbit(r))
				s = max(s, ans[r]);
		}
		return s;
	}
}bt;

接下来上题吧

HDU-1754

solution1:

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
/*********************************************************
Flie Name: hdu1754.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年11月21日 星期四 21时08分37秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
#define lowbit(x) ((-x)&x)
#define Clear (++Ti)
using namespace std;

const int inf = 0x3f3f3f3f, Ma = 2e5 + 100;

int val[Ma];

struct SegTree{
	int Max[Ma << 2];
	void build(int o, int l, int r){
		if(l == r){Max[o] = val[l];return ;}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
	}
	void update(int o, int l, int r, int pos, int val){
		if(l == r){Max[o] = val;return ;}
		int mid = (l + r) >> 1;
		if(pos <= mid)update(o << 1, l, mid, pos, val);
		else update(o << 1 | 1, mid + 1, r, pos, val);
		Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
	}
	int qMax(int o, int l, int r, int L, int R){
		if(l > R || r < L)return -inf;
		if(l >= L && r <= R)return Max[o];
		int mid = (l + r) >> 1;
		return max(qMax(o << 1, l, mid, L, R), qMax(o << 1 | 1, mid + 1, r, L, R));
	}
}st;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	while(cin >> n >> m){
		for(int i = 1; i <= n; i++)
			cin >> val[i];
		st.build(1, 1, n);
		while(m--){
			int l, r;
			char com;
			cin >> com >> l >> r;
			if(com == 'U')st.update(1, 1, n, l, r);
			else if(com == 'Q')cout << st.qMax(1, 1, n, l, r) << '\n';
			else assert(false);
		}
	}
    
    return 0;
}

solution2:

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
/*********************************************************
Flie Name: hdu1754.cpp
Author: Liupo
Email: lanzongwei541@gmail.com
Creat time: 2019年11月21日 星期四 21时08分37秒
*********************************************************/
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define seg(i) i.begin(), i.end()
#define Mem(i) memset(i, 0, sizeof(i))
#define lowbit(x) ((-x)&x)
#define Clear (++Ti)
using namespace std;

const int inf = 0x3f3f3f3f, Ma = 2e5 + 100;

int val[Ma];

struct BitTree{
	int ans[Ma];
	void init(){
		memset(ans, 0, sizeof(ans));
	}
	void change(int pos, int va){
		val[pos] = va;
		for(; pos < Ma; pos += lowbit(pos)){
			ans[pos] = val[pos];
			int t = lowbit(pos);
			for(int i = 1; i < t; i <<= 1)
				ans[pos] = max(ans[pos], ans[pos - i]);
		}
	}
    int Max(int l, int r){
		int s = -inf;
		while(l <= r){
			s = max(s, val[r]);
			r--;
			for(; r - lowbit(r) >= l; r -= lowbit(r))
				s = max(s, ans[r]);
		}
		return s;
	}
}bt;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	while(cin >> n >> m){
		bt.init();
		for(int t, i = 1; i <= n; i++)
			cin >> t, bt.change(i, t);
		while(m--){
			int l, r;
			char com;
			cin >> com >> l >> r;
			if(com == 'U')bt.change(l, r);
			else if(com == 'Q')cout << bt.Max(l, r) << '\n';
			else assert(false);
		}
	}
    
    return 0;
}

区间修改 区间查询

Comments

⬆︎TOP