# # 线段树

## # 什么是线段树

G = Graph({0: [1, 2], 1: [3, 4], 2: [5, 6]})
G.relabel({0: '[1,4]', 1: '[3,4]', 2: '[1,2]', 3: '[4,4]', 4: '[3,3]', 5: '[2,2]', 6: '[1,1]'})
P = G.plot(vertex_size=1500, layout='tree', tree_root='[1,4]', tree_orientation='down')
P.show()

1
2
3
4

## # 练习题

### # 模板题：CF EDU - Segment Tree for the Minimum (opens new window)

fun readInts(): List<Int> {
}

class SegmentTree(private val a: List<Int>) {
private val len = a.size * 4
private val s = LongArray(len)

private fun calc(idx: Int) {
s[idx] = s[idx shl 1].coerceAtMost(s[idx shl 1 xor 1])
}

fun build(idx: Int, l: Int, r: Int) {
if (l == r)
s[idx] = a[l - 1].toLong()
else {
val mid = (l + r) shr 1
build(idx shl 1, l, mid)
build(idx shl 1 xor 1, mid + 1, r)
calc(idx)
}
}

fun update(idx: Int, pos: Int, v: Int, cl: Int, cr: Int) {
if (cl == pos && cl == cr) {
s[idx] = v.toLong()
return
}
val mid = (cl + cr) shr 1
if (pos <= mid)
update(idx shl 1, pos, v, cl, mid)
else
update(idx shl 1 xor 1, pos, v, mid + 1, cr)
calc(idx)
}

fun query(idx: Int, l: Int, r: Int, cl: Int, cr: Int): Long {
if (cl >= l && cr <= r)
return s[idx]
var ans = Long.MAX_VALUE
val mid = (cl + cr) shr 1
if (l <= mid)
ans = ans.coerceAtMost(query(idx shl 1, l, r, cl, mid))
if (mid < r)
ans = ans.coerceAtMost(query(idx shl 1 xor 1, l, r, mid + 1, cr))
return ans
}
}

fun main() {
st.build(1, 1, n)
val ans = mutableListOf<String>()
for (i in 0 until m) {
val (op, v1, v2) = readInts()
if (op == 1)
st.update(1, v1 + 1, v2, 1, n)
else
ans.add(st.query(1, v1 + 1, v2, 1, n).toString())
}
println(ans.joinToString("\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
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

### # 模板题：洛谷 P3372 - 线段树 1 (opens new window)

#include <iostream>
#define lson(idx) (idx << 1)
#define rson(idx) (idx << 1 | 1)
#define MAXN 100005
typedef long long ll;
using namespace std;
struct Node {
ll sum = 0, lazy = 0;
int l, r;
} s[MAXN << 2];
int a[MAXN];

void calc(int idx) {
s[idx].sum = 0;
for (int i = lson(idx); i <= rson(idx); ++i)
s[idx].sum += s[i].sum;
}

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r) {
s[idx].sum = a[l];
return;
}
int mid = (l + r) >> 1;
if (l <= mid)
build(lson(idx), l, mid);
if (mid < r)
build(rson(idx), mid + 1, r);
calc(idx);
}

void pushdown(int idx) {
if (s[idx].lazy == 0)
return;
for (int i = lson(idx); i <= rson(idx); ++i) {
s[i].sum += s[idx].lazy * (s[i].r - s[i].l + 1);
s[i].lazy += s[idx].lazy;
}
s[idx].lazy = 0;
}

void update(int idx, int l, int r, int delta) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].sum += delta * (s[idx].r - s[idx].l + 1);
s[idx].lazy += delta;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson(idx), l, r, delta);
if (mid < r)
update(rson(idx), l, r, delta);
calc(idx);
}

ll query(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].sum;
pushdown(idx);
ll ans = 0;
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
ans += query(lson(idx), l, r);
if (mid < r)
ans += query(rson(idx), l, r);
return ans;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int x;
cin >> x;
update(1, l, r, x);
} else
cout << query(1, l, r) << 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
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

#include <iostream>
#define lson(idx) (idx << 1)
#define rson(idx) (idx << 1 | 1)
#define MAXN 100005
typedef long long ll;
using namespace std;
struct Node {
ll sum = 0, lazy = 0;
int l, r;
} s[MAXN << 2];
int a[MAXN];

void calc(int idx) {
s[idx].sum = 0;

// 注意在pushup的时候带上孩子节点的懒标记值
for (int i = lson(idx); i <= rson(idx); ++i)
s[idx].sum += s[i].sum + s[i].lazy * (s[i].r - s[i].l + 1);
}

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r) {
s[idx].sum = a[l];
return;
}
int mid = (l + r) >> 1;
if (l <= mid)
build(lson(idx), l, mid);
if (mid < r)
build(rson(idx), mid + 1, r);
calc(idx);
}

void update(int idx, int l, int r, int delta) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].lazy += delta;
return;
}
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson(idx), l, r, delta);
if (mid < r)
update(rson(idx), l, r, delta);
calc(idx);
}

ll query(int idx, int l, int r, ll lz) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].sum + (lz + s[idx].lazy) * (s[idx].r - s[idx].l + 1);
ll ans = 0;
int mid = (s[idx].l + s[idx].r) >> 1;

// 懒标记值自上而下逐层累加
if (l <= mid)
ans += query(lson(idx), l, r, lz + s[idx].lazy);
if (mid < r)
ans += query(rson(idx), l, r, lz + s[idx].lazy);
return ans;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int x;
cin >> x;
update(1, l, r, x);
} else
cout << query(1, l, r, 0) << 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
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

### #SPOJ - GSS1 (opens new window)

• 最大和
• 最大前缀和
• 最大后缀和
• 总和

• 总和可以直接由左右区间总和相加得到。
• 最大前缀可能来自左区间的最大前缀，或整个左区间加上右区间的最大前缀。
• 最大后缀可能来自右区间的最大后缀，或整个右区间加上左区间的最大后缀。
• 最大和可能是最大前缀，最大后缀，或左区间的最大后缀加上右区间的最大前缀，或左区间的最大和，或右区间的最大和。

#include <iostream>
#define lson (idx << 1)
#define rson (idx << 1 | 1)
#define INF 0x3f3f3f3f
#define MAXN 50005

using namespace std;
struct Node {
int l = 0, r = 0, lhi = 0, rhi = 0, hi = 0, sum = 0;
} s[MAXN << 2];
int a[MAXN];

Node merge(Node l, Node r) {
Node ret;
ret.l = l.l;
ret.r = r.r;
ret.sum = l.sum + r.sum;
ret.lhi = max(l.lhi, l.sum + r.lhi);
ret.rhi = max(r.rhi, l.rhi + r.sum);
ret.hi = max(max(max(ret.lhi, ret.rhi), max(l.hi, r.hi)), l.rhi + r.lhi);
return ret;
}

void calc(int idx) { s[idx] = merge(s[lson], s[rson]); }

void build(int idx, int l, int r) {
if (l == r) {
s[idx].l = l, s[idx].r = r;
s[idx].hi = s[idx].lhi = s[idx].rhi = s[idx].sum = a[r];
return;
}

int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
calc(idx);
}

Node query(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx];
Node ans;
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
ans = query(lson, l, r);
if (mid + 1 <= r) {
Node right = query(rson, l, r);
if (!ans.l)
return right;
ans = merge(ans, right);
}
return ans;
}

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
build(1, 1, n);
int m;
cin >> m;
for (int i = 1; i <= m; ++i) {
int l, r;
cin >> l >> r;
cout << query(1, l, r).hi << 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68