线段树

sdjasj

单点修改区间查询

区间和

给定长度为$N$的数列$A$,以及$M$条指令,每条指令可能是以下两种之一:

  1. 1 x y,查询区间$[x,y]$ 中的最大连续子段和
  2. 2 x y,把$A[x]$改成 $y$。

对于每个查询指令,输出一个整数表示答案。

输入格式

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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 5e5 + 7;

typedef struct {
int l, r;
int lmax, rmax, sum, tmax;
} Node;

Node t[4 * N];
int a[N];

void pushup(int u) {
Node& root = t[u], left = t[u * 2], right = t[u * 2 + 1];
root.lmax = max(left.lmax, left.sum + right.lmax);
root.rmax = max(right.rmax, right.sum + left.rmax);
root.sum = left.sum + right.sum;
root.tmax = max(left.tmax, max(right.tmax, left.rmax + right.lmax));
}

void pushup(Node& root, Node& left, Node& right) {
root.lmax = max(left.lmax, left.sum + right.lmax);
root.rmax = max(right.rmax, right.sum + left.rmax);
root.sum = left.sum + right.sum;
root.tmax = max(left.tmax, max(right.tmax, left.rmax + right.lmax));
}

void build(int u, int l, int r) {
t[u] = {l, r};
if (l == r) {
t[u].sum = t[u].lmax = t[u].rmax = t[u].tmax = a[l];
return;
}
int mid = l + r >> 1;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
pushup(u);
}

Node query(int u, int l, int r) {
if (t[u].l >= l && t[u].r <= r) {
return t[u];
}
int mid = t[u].l + t[u].r >> 1;
if (r <= mid) {
return query(u * 2, l, r);
}
if (l > mid) {
return query(u * 2 + 1, l, r);
}
Node res;
Node left = query(u * 2, l , r);
Node right = query(u * 2 + 1, l, r);
pushup(res, left, right);
return res;
}

void modify(int u, int y, int x) {
if (t[u].l == y && t[u].r == y) {
t[u].lmax = t[u].rmax = t[u].sum = t[u].tmax = x;
return;
}

int mid = t[u].l + t[u].r >> 1;
if (y <= mid) {
modify(u * 2, y, x);
} else {
modify(u * 2 + 1, y, x);
}
pushup(u);
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (m--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
if (x > y) swap(x, y);
cout << query(1, x, y).tmax << endl;
} else {
modify(1, x, y);
}
}
return 0;
}

区间最大值

给定一个正整数数列$a_1,a_2,…,a_n$,每一个数都在 $0 \sim p-1$ 之间。

可以对这列数进行两种操作:

  1. 添加操作:向序列后添加一个数,序列长度变成 $n+1$;
  2. 询问操作:询问这个序列中最后$L$个数中最大的数是多少。

程序运行的最开始,整数序列为空。

一共要对整数序列进行$m$次操作。

写一个程序,读入操作的序列,并输出询问操作的答案

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200007;

struct {
int l;
int r;
int v;
} t[N * 4];

int m, p, n, a;

void pushup(int u) {
t[u].v = max(t[u << 1].v, t[u << 1 | 1].v);
}

void build(int u, int l, int r) {
t[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l ,mid);
build(u << 1 | 1, mid + 1, r);
}

void update(int u, int x, int v) {
if (t[u].l == x && t[u].r == x) t[u].v = v;
else {

int mid = t[u].l + t[u].r >> 1;
if (mid >= x) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
pushup(u);
}
}

int query(int u, int l, int r) {
if (l <= t[u].l && r >= t[u].r) return t[u].v;
int ans = 0;
int mid = t[u].l + t[u].r >> 1;
if (l <= mid) ans = query(u << 1, l ,r);
if (r > mid) ans = max(ans, query(u << 1 | 1, l ,r));
return ans;
}

int main() {
cin >> m >>p;
build(1, 1, m);
while (m--) {
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'Q') {
a = query(1, n - x + 1, n);
cout << a << endl;
} else {
update(1, ++n, ((LL)x + a) % p);
}
}
return 0;
}

区间gcd

给定一个长度为 N的数列 A,以及 M 条指令,每条指令可能是以下两种之一:

  1. C l r d,表示把$ A[l],A[l+1],…,A[r] $都加上 。
  2. Q l r,表示询问$ A[l],A[l+1],…,A[r] $的最大公约数(GCD)。

对于每个询问,输出一个整数表示答案。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node
{
int l, r;
LL sum, d;
}tr[N * 4];

LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}

void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}

void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
if (l == r)
{
LL b = w[r] - w[r - 1];
tr[u] = {l, r, b, b};
}
else
{
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u, int x, LL v)
{
if (tr[u].l == x && tr[u].r == x)
{
LL b = tr[u].sum + v;
tr[u] = {x, x, b, b};
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}

Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
build(1, 1, n);

int l, r;
LL d;
char op[2];
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
auto left = query(1, 1, l);
Node right({0, 0, 0, 0});
if (l + 1 <= r) right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(left.sum, right.d)));
}
else
{
scanf("%lld", &d);
modify(1, l, d);
if (r + 1 <= n) modify(1, r + 1, -d);
}
}

return 0;
}

区间修改区间查询(懒标记)

区间和(区间加)

给定一个长度为 N的数列 A,以及 M 条指令,每条指令可能是以下两种之一:

  1. C l r d,表示把 $A[l],A[l+1],…,A[r] $都加上 d。
  2. Q l r,表示询问数列中第 $l\sim r$个数的和。

对于每个询问,输出一个整数表示答案。

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
#include <vector>
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
struct Node {
int l, r;
LL sum, add;
} tr[4 * N];
int a[N];

void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) {
left.add += root.add;
left.sum += (LL)(left.r - left.l + 1) * root.add;
right.add += root.add;
right.sum += (LL) (right.r - right.l + 1) * root.add;
root.add = 0;
}
}

void build(int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, a[l], 0};
} else {
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
tr[u].add = 0;
}
}

void modify(int u, int l, int r, int x) {
if (l <= tr[u].l && r >= tr[u].r) {
tr[u].sum += (LL) x * (tr[u].r - tr[u].l + 1);
tr[u].add += x;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if (l <= mid) {
modify(u << 1, l, r, x);
}
if (r > mid) {
modify(u << 1 | 1, l, r, x);
}
pushup(u);
}

LL query(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r) {
return tr[u].sum;
}
int mid = (tr[u].l + tr[u].r) >> 1;
LL ans = 0;
pushdown(u);
if (l <= mid) ans += query(u << 1, l, r);
if (r > mid) ans += query(u << 1 | 1, l, r);
return ans;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (m--) {
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l , &r);
if (op[0] == 'Q') {
cout << query(1, l, r) << endl;
} else {
scanf("%d", &d);
modify(1, l, r, d);
}
}
return 0;
}

区间和(区间乘和加)

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。

有长为 N 的数列,不妨设为 $a_1,a_2,…,a_N$。

有如下三种操作形式:

  1. 把数列中的一段数全部乘一个值;
  2. 把数列中的一段数全部加一个值;
  3. 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 P的值。
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
#include <vector>
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
int p;
struct Node {
int l, r;
LL sum, add, mul;
} tr[4 * N];
int a[N];

void cal(int u, LL add, LL mul) {
tr[u].sum = ((LL) tr[u].sum * mul + (LL) (tr[u].r - tr[u].l + 1) * add) % p;
tr[u].mul = (LL) (tr[u].mul * mul) % p;
tr[u].add = ((LL) (tr[u].add * mul) % p + add) % p;
}

void pushup(int u) {
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown(int u) {
cal(u << 1, tr[u].add, tr[u].mul);
cal(u << 1 | 1, tr[u].add, tr[u].mul);
tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r) {
if (l == r) {
tr[u] = {l, r, a[l], 0, 1};
} else {
tr[u] = {l, r, 0, 0, 1};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u, int l, int r, int add, int mul) {
if (l <= tr[u].l && r >= tr[u].r) {
cal(u, add, mul);
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if (l <= mid) {
modify(u << 1, l, r, add, mul);
}
if (r > mid) {
modify(u << 1 | 1, l, r, add, mul);
}
pushup(u);
}

LL query(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r) {
return tr[u].sum;
}
int mid = (tr[u].l + tr[u].r) >> 1;
LL ans = 0;
pushdown(u);
if (l <= mid) ans = query(u << 1, l, r) % p;
if (r > mid) ans = (ans + query(u << 1 | 1, l, r)) % p;
return ans;
}

int main() {
int n, m;
cin >> n >> p;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
cin >> m;
build(1, 1, n);
while (m--) {
int op;
int l, r, d;
scanf("%d%d%d", &op, &l , &r);
if (op == 1) {
scanf("%d", &d);
modify(1, l, r, 0, d);
} else if (op == 2) {
scanf("%d", &d);
modify(1, l, r, d, 1);
} else {
cout << query(1, l, r) << endl;
}
}
return 0;
}

应用

1.区间和

左右子区间相加即可

2.区间最大数

左右区间最大数取max

3.区间最大子段和

左区间左端点开始的最大子段和 右区间右端点开始的最大子段和 左区间右端点开始的最大子段和+右区间左端点开始的最大子段和 三者取max

  • 標題: 线段树
  • 作者: sdjasj
  • 撰寫于: 2023-02-01 16:38:19
  • 更新于: 2023-02-01 17:49:13
  • 連結: https://redefine.ohevan.com/2023/02/01/线段树/
  • 版權宣告: 本作品采用 CC BY-NC-SA 4.0 进行许可。
 留言