数据结构和算法模板 in C++

不知道我还有没有搞竞赛的那一天了(悲)

数据结构

树状数组

普通版树状数组(单点加、区间求和)

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
// https://www.luogu.com.cn/problem/P3374
#include <iostream>
#define MAXN 500000
using namespace std;
int n, m;
long long c[MAXN + 5];
inline int lowbit(int x) { return x & -x; }
void add(int pos, long long val)
{
while (pos <= n)
{
c[pos] += val;
pos += lowbit(pos);
}
}
long long sum(int pos)
{
long long ans = 0;
while (pos > 0)
{
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
long long x;
for (int i = 1; i <= n; i++)
{
cin >> x;
add(i, x);
}
while (m--)
{
int opt;
cin >> opt;
if (opt == 1)
{
int x, k;
cin >> x >> k;
add(x, k);
}
else if (opt == 2)
{
int x, y;
cin >> x >> y;
cout << sum(y) - sum(x - 1) << endl;
}
}
return 0;
}

树状数组 with 前缀和(区间加、单点查)

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
// https://www.luogu.com.cn/problem/P3368
#include <iostream>
#define MAXN 500000
using namespace std;
int n, m;
long long c[MAXN + 5];
inline int lowbit(int x) { return x & -x; }
void add(int pos, long long val)
{
while (pos <= n)
{
c[pos] += val;
pos += lowbit(pos);
}
}
long long sum(int pos)
{
long long ans = 0;
while (pos > 0)
{
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
long long x, y = 0;
for (int i = 1; i <= n; i++)
{
cin >> x;
add(i, x - y);
y = x;
}
while (m--)
{
int opt;
cin >> opt;
if (opt == 1)
{
int x, y, k;
cin >> x >> y >> k;
add(x, k);
add(y + 1, -k);
}
else if (opt == 2)
{
int x;
cin >> x;
cout << sum(x) << endl;
}
}
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
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
// http://acm.hdu.edu.cn/showproblem.php?pid=1754
#include <iostream>
#define MAXN 200005
using namespace std;
int a[MAXN];
struct node
{
int l, r, m;
int max;
} nodes[MAXN * 4];
inline void maintain(int p)
{
node &no = nodes[p];
if (no.l != no.r)
no.max = max(nodes[p << 1].max, nodes[p << 1 | 1].max);
}
void init(int l, int r, int p = 1)
{
node &no = nodes[p];
no.l = l, no.r = r, no.m = (l + r) / 2;
if (l == r)
no.max = a[l];
else
{
init(l, no.m, p << 1);
init(no.m + 1, r, p << 1 | 1);
maintain(p);
}
}
void update(int pos, int val, int p = 1)
{
node &no = nodes[p];
if (no.l == no.r)
no.max = val;
else
{
if (pos <= no.m)
update(pos, val, p << 1);
else
update(pos, val, p << 1 | 1);
maintain(p);
}
}
int query(int l, int r, int p = 1)
{
node &no = nodes[p];
if (no.l == l && no.r == r)
return no.max;
else
{
int ans = INT_MIN;
if (l <= no.m)
ans = max(ans, query(l, min(no.m, r), p << 1));
if (no.m + 1 <= r)
ans = max(ans, query(max(no.m + 1, l), r, p << 1 | 1));
return ans;
}
}
int main()
{
ios::sync_with_stdio(false);

int n, m;
while (cin >> n >> m)
{
for (int i = 1; i <= n; i++)
cin >> a[i];
init(1, n);

char opt;
int a, b;
while (m--)
{
cin >> opt >> a >> b;
if (opt == 'Q')
cout << query(a, b) << endl;
else if (opt == 'U')
update(a, b);
}
}

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
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
// https://www.luogu.com.cn/problem/P3372
#include <iostream>
#define MAXN 100005
using namespace std;
int n, m, a[MAXN];
struct node
{
int l, r, m;
long long inc = 0, sum = 0;
} nodes[MAXN * 4];
void init(int l, int r, int p = 1)
{
node &no = nodes[p];
no.l = l, no.r = r, no.m = (l + r) / 2;
if (l == r)
no.sum = a[l];
else
{
init(l, no.m, p * 2);
init(no.m + 1, r, p * 2 + 1);
no.sum = nodes[p * 2].sum + nodes[p * 2 + 1].sum;
}
}
void add(int l, int r, long long val, int p = 1)
{
if (l > r)
return;
node &no = nodes[p];
no.sum += (r - l + 1) * val;
if (l == no.l && r == no.r)
no.inc += val;
else
{
add(l, min(no.m, r), val, p * 2);
add(max(no.m + 1, l), r, val, p * 2 + 1);
}
}
long long sum(int l, int r, int p = 1)
{
node &no = nodes[p];
if (l == no.l && r == no.r)
return no.sum;
else
{
long long ans = no.inc * (r - l + 1);
if (l <= no.m)
ans += sum(l, min(no.m, r), p * 2);
if (no.m + 1 <= r)
ans += sum(max(no.m + 1, l), r, p * 2 + 1);
return ans;
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
init(1, n);
while (m--)
{
int opt, x, y;
cin >> opt >> x >> y;
if (opt == 1)
{
long long k;
cin >> k;
add(x, y, k);
}
else
cout << sum(x, y) << endl;
}
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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
// https://www.luogu.com.cn/problem/P3373
#include <iostream>
#define MAXN 100005
using namespace std;
int n, m, a[MAXN], ha;
struct node
{
int l, r, m;
long long inc = 0, time = 1, sum = 0;
// 当乘法和加法标记同时存在时,应理解为先乘后加
} nodes[MAXN * 4];
void maintain(int p)
{
node &no = nodes[p];
if (no.l == no.r)
no.sum = no.inc;
else
{
node &nol = nodes[p * 2], &nor = nodes[p * 2 + 1];
no.sum = (nol.sum + nor.sum) % ha;
no.sum = (no.sum + (no.r - no.l + 1) % ha * no.inc % ha) % ha;
no.sum = no.sum * no.time % ha;
}
}
void pushdown(int p)
{
node &no = nodes[p], &nol = nodes[p * 2], &nor = nodes[p * 2 + 1];

nol.time = nol.time * no.time % ha;
nol.inc = (nol.inc * no.time % ha + no.inc) % ha;
nol.sum = (nol.sum * no.time % ha + no.inc * (nol.r - nol.l + 1) % ha) % ha;

nor.time = nor.time * no.time % ha;
nor.inc = (nor.inc * no.time % ha + no.inc) % ha;
nor.sum = (nor.sum * no.time % ha + no.inc * (nor.r - nor.l + 1) % ha) % ha;

no.inc = 0;
no.time = 1;
}
void init(int l, int r, int p = 1)
{
node &no = nodes[p];
no.l = l, no.r = r, no.m = (l + r) / 2;
if (l == r)
no.inc = a[l] % ha;
else
{
init(l, no.m, p * 2);
init(no.m + 1, r, p * 2 + 1);
}
maintain(p);
}
void add(int l, int r, long long val, int p = 1)
{
node &no = nodes[p];
if (l == no.l && r == no.r)
{
no.inc = (no.inc + val) % ha;
no.sum = (no.sum + (r - l + 1) % ha * val % ha) % ha;
}
else
{
pushdown(p);
if (l <= no.m)
add(l, min(no.m, r), val, p * 2);
if (no.m + 1 <= r)
add(max(no.m + 1, l), r, val, p * 2 + 1);
maintain(p);
}
}
void mul(int l, int r, long long val, int p = 1)
{
node &no = nodes[p];
if (l == no.l && r == no.r)
{
no.time = no.time * val % ha;
no.inc = no.inc * val % ha;
no.sum = no.sum * val % ha;
}
else
{
pushdown(p);
if (l <= no.m)
mul(l, min(no.m, r), val, p * 2);
if (no.m + 1 <= r)
mul(max(no.m + 1, l), r, val, p * 2 + 1);
maintain(p);
}
}
long long sum(int l, int r, int p = 1)
{
node &no = nodes[p];
if (l == no.l && r == no.r)
return no.sum;
else
{
pushdown(p);
long long ans = 0;
if (l <= no.m)
ans = (ans + sum(l, min(no.m, r), p * 2)) % ha;
if (no.m + 1 <= r)
ans = (ans + sum(max(no.m + 1, l), r, p * 2 + 1)) % ha;
return ans;
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> ha;
for (int i = 1; i <= n; i++)
cin >> a[i];
init(1, n);
while (m--)
{
int opt, x, y;
cin >> opt >> x >> y;
if (opt == 1)
{
long long k;
cin >> k;
mul(x, y, k);
}
else if (opt == 2)
{
long long k;
cin >> k;
add(x, y, k);
}
else
cout << sum(x, y) << endl;
}
return 0;
}
Author: ssttkkl
Link: https://ssttkkl.github.io/uncategorized/2019/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF-in-CPP/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.