Articles
83
Tags
38
Categories
6
Home
Archives
Tags
Categories
Link
Gallery
About
Catalog
  1. 1. ST表
  2. 2. 树状数组
    1. 2.1. 树状数组1
  3. 3. 线段树
    1. 3.1. 线段树1
    2. 3.2. 线段树2
Aurora的模板集合
|模板
Post View:

ST表

传送门1：P3865 【模板】ST表

传送门2：ST 表-OI Wiki

code:

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<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");

using namespace std;

int read() {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n, m, x, y, s, f[100005][23], logn[100005];

void pre() {
	logn[1] = 0;
	logn[2] = 1;
	for(int i = 3; i <= 100005; i++) logn[i] = logn[i >> 1] + 1;
}

int main() {
	n = read(); m = read();
	for(int i = 1; i <= n; i++) f[i][0] = read();
	pre();
	for(int j = 1; j <= 21; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
	while(m--) {
		x = read(); y = read();
		s = logn[y - x + 1];
		printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
	}
    return 0;
}

树状数组

树状数组1

传送门1：P3374 【模板】树状数组 1

传送门2：树状数组-OI Wiki

操作：

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

code:

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");

using namespace std;

int read() {
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n, m, x, y, k, opt, c[500005], t[500005];

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

void build() {
	for(int i = 1; i <= n; i++) {
		t[i] = t[i] + c[i];
		int j = i + lowbit(i);
		if(j <= n) t[j] = t[j] + t[i];
	}
}

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

int query(int x) {
	int ans = 0;
	while(x) {
		ans = ans + t[x];
		x = x - lowbit(x);
	}
	return ans;
}

int main() {
	n = read(); m = read();
	for(int i = 1; i <= n; i++) c[i] = read();
	build();
	while(m--) {
		opt = read(); x = read();
		if(opt == 1) {
			k = read();
			update(x, k);
		}
		else {
			y = read();
			printf("%d\n", query(y) - query(x - 1)); 
		}
	}
    return 0;
}

线段树

线段树1

传送门：P3372 【模板】线段树 1

操作：

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

code:

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
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");

using namespace std;

ll read() {
    register ll x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

struct TREE {
	ll sum, lazy;
}tre[400005];

ll n, m, x, y, k, opt;

void build(ll u, ll l, ll r) {
	if(l == r) {
		tre[u].sum = read();
		return ;
	}
	ll lson = u << 1, rson = (u << 1) + 1, mid = (l + r) >> 1;
	build(lson, l, mid); build(rson, mid + 1, r);
	tre[u].sum = tre[lson].sum + tre[rson].sum;
}

void pushdown(ll u, ll l, ll r) {
	if(tre[u].lazy == 0 || l == r) return;
	ll lson = (u << 1), rson = (u << 1) + 1, mid = (l + r) >> 1;
	tre[lson].lazy += tre[u].lazy; tre[lson].sum = tre[lson].sum + tre[u].lazy * (mid - l + 1);
	tre[rson].lazy += tre[u].lazy; tre[rson].sum = tre[rson].sum + tre[u].lazy * (r - mid);
	tre[u].lazy = 0;
}

void update(ll u, ll l, ll r, ll x, ll y, ll k) {
	if(l >= x && r <= y) {
		tre[u].lazy = tre[u].lazy + k;
		tre[u].sum = tre[u].sum + k * (r - l + 1);
		return ;
	}
	ll lson = u << 1, rson = (u << 1) + 1, mid = (l + r) >> 1;
	pushdown(u, l, r);
	if(x <= mid) update(lson, l, mid, x, y, k);
	if(y > mid) update(rson, mid + 1, r, x, y, k);
	tre[u].sum = tre[lson].sum + tre[rson].sum;
}

ll query(ll u, ll l, ll r ,ll x, ll y) {
	if(l >= x && r <= y) return tre[u].sum;
	ll lson = u << 1, rson = (u << 1) + 1, mid = (l + r) >> 1, t1 = 0, t2 = 0;
	pushdown(u, l ,r);
	if(x <= mid) t1 = query(lson, l, mid, x, y);
	if(y > mid) t2 = query(rson, mid + 1, r, x, y);
	return t1 + t2;
}

int main() {
	n = read(); m = read();
	build(1, 1, n);
	while(m--) {
		opt = read(); x = read(); y = read();
		if(opt == 1) {
			k = read();
			update(1, 1, n, x, y, k);
		}
		if(opt == 2) printf("%lld\n", query(1, 1, n, x, y));
	}
    return 0;
}

线段树2

传送门：P3373 【模板】线段树 2

操作：

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

code:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define int long long
#define INF 0x7fffffff
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");
#define lson tre << 1
#define rson tre << 1 | 1

using namespace std;

long long read()
{
	register long long x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,p,opt,x,y,z;

struct node {
	int sum,lazy1,lazy2;
}t[1000005];

void build(int tre,int l,int r) {
	t[tre].lazy2 = 1;
	if(l == r) {
		t[tre].sum = read() % p;
		return ;
	}
	int mid = (l + r) >> 1;
	build(lson,l,mid); build(rson,mid + 1,r);
	t[tre].sum = (t[lson].sum + t[rson].sum) % p;
}

void pushdown(int tre,int l,int r) {
	int mid = (l + r) >> 1;
	t[lson].lazy1 = (t[lson].lazy1 * t[tre].lazy2 + t[tre].lazy1) % p;
	t[rson].lazy1 = (t[rson].lazy1 * t[tre].lazy2 + t[tre].lazy1) % p;
	t[lson].lazy2 = (t[lson].lazy2 * t[tre].lazy2) % p;
	t[rson].lazy2 = (t[rson].lazy2 * t[tre].lazy2) % p;
	t[lson].sum = ((t[lson].sum * t[tre].lazy2) % p + (t[tre].lazy1 * (mid - l + 1)) % p) % p;
	t[rson].sum = ((t[rson].sum * t[tre].lazy2) % p + (t[tre].lazy1 * (r - mid)) % p) % p;
	t[tre].lazy1 = 0; t[tre].lazy2 = 1;
}

void updata1(int tre,int l,int r,int x,int y,int z) {
	if(l >= x && r <= y) {
		t[tre].sum = (t[tre].sum + (r - l + 1) * z) % p;
		t[tre].lazy1 = (t[tre].lazy1 + z) % p;
		return ;
	}
	pushdown(tre,l,r);
	int mid = (l + r) >> 1;
	if(x <= mid) updata1(lson,l,mid,x,y,z);
	if(y > mid) updata1(rson,mid + 1,r,x,y,z);
	t[tre].sum = (t[lson].sum + t[rson].sum) % p;
}

void updata2(int tre,int l,int r,int x,int y,int z) {
	if(l >= x && r <= y) {
		t[tre].sum = (t[tre].sum * z) % p;
		t[tre].lazy1 = (t[tre].lazy1 * z) % p;
		t[tre].lazy2 = (t[tre].lazy2 * z) % p;
		return ;
	}
	pushdown(tre,l,r);
	int mid = (l + r) >> 1;
	if(x <= mid) updata2(lson,l,mid,x,y,z);
	if(y > mid) updata2(rson,mid + 1,r,x,y,z);
	t[tre].sum = (t[lson].sum + t[rson].sum) % p;
}

int query(int tre,int l,int r,int x,int y) {
	if(l >= x && r <= y) return t[tre].sum;
	pushdown(tre,l,r);
	int mid = (l + r) >> 1,t1 = 0,t2 = 0;
	if(x <= mid) t1 = query(lson,l,mid,x,y);
	if(y > mid) t2 = query(rson,mid + 1,r,x,y);
	return (t1 + t2) % p;
}

signed main()
{
	n = read(); m = read(); p = read();
	build(1,1,n);
	for(int i = 1; i <= m; i++) {
		opt = read(); x = read(); y = read();
		if(opt == 1) z = read(), updata2(1,1,n,x,y,z);
		if(opt == 2) z = read(), updata1(1,1,n,x,y,z);
		if(opt == 3) printf("%lld\n",query(1,1,n,x,y));
	}
    return 0;
}
Author: wflight
Link: http://yoursite.com/2020/08/03/Aurora的模板集合/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
st表 树状数组 线段树
Donate
  • 微信
  • 支付寶
Recommend
求逆序对数的三种方法
题解 P5816 【[CQOI2010]内部白点】
Comment
繁