什么是线段树

以下内容摘自OI-Wiki

线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在$O(\log N)$的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。

线段树维护的信息,需要满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用懒惰标记时,标记也要满足可加性(例如取模就不满足可加性,对$4$取模然后对$3$取模,两个操作就不能合并在一起做)。

线段树

题目链接

【模板】线段树 1

代码实现

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
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll a[100005];
ll tree[100005]; // 左子树下标p*2,右子树下标p*2+1
ll lazy[100005]; // 懒惰标签

namespace st {
// p: 当前数组的下标
// l, r: 区间l-r,在数组a里面
void build(int p, int l, int r) {
lazy[p] = 0; // 懒惰标签清空

if (l == r) { // 如果已经到了最小的部分
tree[p] = a[l]; // 把当前数组a的值赋值给线段树tree[p]
return;
}

int mid = (l + r) / 2;
build(p * 2, l, mid); // 建立左子树
build(p * 2 + 1, mid + 1, r); // 建立右子树
tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 当前数的值等于子树的和
}

// len: 下传的子树区间大小
void pushdown(int p, int len) {
// 子树节点的懒惰标记加上父亲节点的懒惰标记
lazy[p * 2] += lazy[p];
lazy[p * 2 + 1] += lazy[p];

// 子树更新区间和
tree[p * 2] += (len - len / 2) * lazy[p];
tree[p * 2 + 1] += (len / 2) * lazy[p];

// 清除父亲节点的懒惰标记
lazy[p] = 0;
}

// x, y: 修改[x,y]这个区间
// num: 修改的值,加上一个数
void change(int p, int l, int r, int x, int y, int num) {
if (x <= l && y >= r) { // [l,r]区间包含了当前区间[x,y]
lazy[p] += num; // 修改区间[l,r]的懒惰标签
tree[p] += (num * ll(r - l + 1)); // 当前区间的区间和加上左右子树的和
return;
}

// 向下搜索
pushdown(p, (r - l + 1)); // 懒惰标记下传(只下穿一层)

int mid = (l + r) / 2;
if (x <= mid)
change(p * 2, l, mid, x, y, num); // 遍历左子树
if (y > mid)
change(p * 2 + 1, mid + 1, r, x, y, num); // 遍历右子树

tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 更新区间和(左子树和右子树的和)
}

// x, y: 需要查询的区间左右界
ll find(int p, int l, int r, int x, int y) {
if (x <= l && y >= r) // 如果区间[l,r]被完整包含在了需要查询的区间[x,y]里面
return tree[p]; // 返回区间[l,r]的区间和
int mid = (l + r) / 2;

if (lazy[p] != 0) // 如果节点含有懒惰标记
pushdown(p, r - l + 1); // 懒惰标记下传

ll re = 0;

if (x <= mid) // 如果需要查询的区间在mid的左边
re += find(p * 2, l, mid, x, y); // 搜索左子树
if (y > mid) // 如果需要查询的区间在mid的右边
re += find(p * 2 + 1, mid + 1, r, x, y); // 搜索右子树

return re;
}

} // namespace st

int main() {
int n, m;
scanf("%d %d", &n, &m);

for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}

st::build(1, 1, n); // 建立线段树

for (int i = 1; i <= m; i++) {
int op, x, y, k;
scanf("%d", &op);
if (op == 1) {
scanf("%d %d %d", &x, &y, &k);
st::change(1, 1, n, x, y, k);
} else if (op == 2) {
scanf("%d %d", &x, &y);
ll ans = st::find(1, 1, n, x, y);
printf("%lld\n", ans);
}
}

return 0;
}

评论