线段树模板+模板题(HDU1166)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1166

原来都是用的别人的模板, 这次自己又重新看了一遍线段树(基础), 重新回顾了一遍, 敲了一遍模板
模板的注释写的蛮详细的, 这里就不讲解线段树了, emmmm

代码

用了懒标记效率会提升很多!!

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
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int node[MAXN<<2], lazy[MAXN<<2];//为什么空间要开节点的4倍 请移步至:https://blog.csdn.net/liqiming100/article/details/82319686
int num[MAXN];
//线段树模板(以区间和为例)
//更新数据
inline void PushUp(int root)
{
node[root] = node[root<<1] + node[root<<1|1];
}
//1.建树
inline void BuildTree(int root, int l, int r) //[l,r]当前节点的区间, root 当前节点的编号
{
if(l == r){
//说明当前已经到达叶子节点
node[root] = num[l]; //建树先左后右
return ;
}
int mid = (l + r) >> 1;
//继续递归建树
BuildTree(root<<1, l, mid);//左
BuildTree(root<<1|1, mid + 1, r);//右

//其他操作(例如更新区间和)
PushUp(root);

}
//2.单点修改
inline void Update(int root, int l, int r, int index, int value)
{
// root 当前节点编号 [l,r] 树的区间范围, index 修改的节点编号, value 修改的值
if(l == r){
//到达当前节点
node[root] += value;
return ;
}
int mid = (l + r) >> 1;
if(index <= mid)
Update(root<<1, l, mid, index, value);
else
Update(root<<1|1, mid + 1, r, index, value);

//修改后记得更新
PushUp(root);
}
//3.区间修改
//区间修改为了优化效率,我们引入'懒标记' lazy, 所以我们需要一个向下推(向叶节点更新的函数)
inline void PushDown(int root, int ln, int rn)
{
// root 当前节点编号, ln 左子树节点个数, rn 右子树节点个数
if(lazy[root]){
//为什么是加上而不是直接赋值, 可能存在连续的进行区间修改
lazy[root<<1] += lazy[root];
lazy[root<<1|1] += lazy[root];
//更新结果
node[root<<1] += lazy[root] * ln;
node[root<<1|1] += lazy[root] * rn;
//清除标记
lazy[root] = 0;
}

}
inline void Update(int root, int l, int r, int L, int R, int value)
{
// root 当前节点的编号, [l,r] 线段树区间, [L,R] 需要修改的区间范围 , value 修改的值
if(L <= l && r <= R){
//说明在修改的区间范围
node[root] += (value * (r - l + 1)); //直接修改这个节点的值(得到当前区间正确的值)
lazy[root] += value; //下面的节点值用lazy来修改
return ;
}
int mid = (l + r) >> 1;
//下推lazy
PushDown(root, mid - l + 1, r - mid);
if(L <= mid)
Update(root<<1, l, mid, L, R, value);
if(R > mid)
Update(root<<1|1, mid + 1, r, L, R, value);

//更新
PushUp(root);
}
//4.区间查询
inline int Query(int root, int l, int r, int L, int R)
{
// root 当前节点的编号, [l,r] 线段树区间, [L,R] 需要修改的区间范围
if(L <= l && r <= R){
//当前区间在查询区间内, 直接返回节点值
return node[root];
}
int mid = (l + r) >> 1;
//下推lazy
PushDown(root, mid - l + 1, r - mid);

int ans = 0;
if(L <= mid)
ans += Query(root<<1, l, mid, L, R);
if(R > mid)
ans += Query(root<<1|1, mid + 1, r, L, R);

return ans;
}
int main()
{
ios::sync_with_stdio(false);
int t;
int n;
string s;
int a, b, c;
while(cin >> t){
for(int i = 1; i <= t; i++){
cout << "Case " << i << ":" << endl;
cin >> n;
for(int j = 1; j <= n; j++){
cin >> num[j];
}
BuildTree(1,1,n);
while(cin >> s && s != "End"){
if(s == "Query"){
cin >> a >> b;
cout << Query(1, 1, n, a, b) << endl;
}
else if(s == "Add"){
cin >> a >> b;
Update(1, 1, n, a, b);
}
else if(s == "Sub"){
cin >> a >> b;
Update(1, 1, n, a, -b);
}
}
}
}

return 0;
}

线段树还有好多应用,看来路还很长啊!!

本文标题:线段树模板+模板题(HDU1166)

文章作者:HKer_YM

发布时间:2019年08月20日 - 02:18:21

最后更新:2020年03月01日 - 12:58:18

原始链接:https://blog.dreams-wj.top/2019/08/20/%E7%BA%BF%E6%AE%B5%E6%A0%91%E6%A8%A1%E6%9D%BF-%E6%A8%A1%E6%9D%BF%E9%A2%98-HDU1166/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。