没有合适的资源?快使用搜索试试~ 我知道了~
首页HH神重构经典:优化线段树教程与实战
HH神重构经典:优化线段树教程与实战
需积分: 1 9 下载量 153 浏览量
更新于2024-07-19
收藏 249KB PDF 举报
本文档是一篇由HH神整理的关于线段树的详细教程,针对早期的一篇点击率较高的文章进行了重新编写,目的是纠正代码风格并更新近年来遇到的新题。HH神强调了线段树编程中的几个关键点: 1. 节点数量计算:线段树的节点数通常比最大区间`maxn`多出4倍,具体而言,节点数至少为`2 * maxn`的下一个最小的2的倍数,这样可以确保效率。 2. 变量命名:为了方便操作,HH神使用`lson`和`rson`分别表示结点的左儿子和右儿子,通过预先定义这些变量,使得代码更加直观。 3. 区间存储优化:以往的做法会额外存储每个节点的区间信息,但HH神发现这并非必要,可以通过在函数调用时传递区间信息来实现,只需稍加参数处理即可。 4. 更新与合并:`PushUP(intrt)`函数负责将子节点的信息向上合并到父节点,确保节点数据的同步;`PushDown(intrt)`则是向下更新给子节点,处理递归过程中的状态。 5. 线段树结构:线段树的问题通常分为四类:单点更新,涉及修改叶子节点并用`PushUP`递归更新;查询操作,如HDU1166敌兵布阵中的区间求和,通过`sum`数组记录区间总和。 6. 代码示例:文档中提供了一个简单的线段树构建和更新的C++代码片段,展示了如何使用`scanf`读取输入值,以及`PushUP`和`build`函数的基本用法。 通过对这些要点的讲解,读者能够掌握HH神对于线段树的高效编码风格和基本操作,这对于理解线段树这一重要数据结构的精髓十分关键。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/9930703/bg5.jpg)
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
if (
l
==
r
) {
sum
[
rt
] ++;
return ;
}
int
m
= (
l
+
r
) >> 1;
if (
p
<=
m
)
update
(
p , lson
);
else
update
(
p , rson
);
PushUP
(
rt
);
}
int
query
(int
L,
int
R,
int
l,
int
r,
int
rt
) {
if (
L
<=
l
&&
r
<=
R
) {
return
sum
[
rt
];
}
int
m
= (
l
+
r
) >> 1;
int
ret
= 0;
if (
L
<=
m
)
ret
+=
query
(
L , R , lson
);
if (
R
>
m
)
ret
+=
query
(
L , R , rson
);
return
ret
;
}
int
x
[
maxn
];
int
main
() {
int
n
;
while (
~
scanf("%d"
,
&
n
)) {
build
(0
, n
- 1
,
1);
int
sum
= 0;
for (int
i
= 0 ;
i
<
n
;
i
++) {
scanf("%d"
,
&
x
[
i
]);
sum
+=
query
(
x
[
i
]
, n
- 1
,
0
, n
- 1
,
1);
update
(
x
[
i
]
,
0
, n
- 1
,
1);
}
int
ret
=
sum
;
for (int
i
= 0 ;
i
<
n
;
i
++) {
sum
+=
n
-
x
[
i
] -
x
[
i
] - 1;
ret
=
min
(
ret , sum
);
}
printf("%d\n"
,ret
);
}
return 0;
}
o hdu2795 Billboard
题意:h*w 的木板,放进一些 1*L 的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去 L
线段树功能:query:区间求最大值的位子(直接把 update 的操作在 query 里做了)
?
View Code CPP
剩余20页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/024998e9a7264628b8e13ba77e737689_zuzhiang.jpg!1)
棉花糖灬
- 粉丝: 1016
- 资源: 23
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 岩石滑动与断层冲击地压:声发射特征分析
- 新时代煤炭工业八大战略新取向剖析
- 开采强度对华亭矿区冲击地压危险性的影响分析
- 新安煤矿探采对比:影响安全生产的关键因素与技术支撑
- 210MW循环流化床锅炉引风机变频改造优化与节能效果
- 浅埋煤层开采沉陷预测:方法应用与影响分析
- 优化巷道过陷落柱支护方案:数值模拟与现场试验
- 坚硬顶板定向断裂爆破技术:安全高效采煤新方案
- 北航2019算法课作业解析:投资策略与凸子多边形优化
- 断层破碎带垮冒下堆积体边界抗力分布关键影响因素
- 哈拉沟选煤厂优化末煤系统提高效率与处理能力
- 瓦斯涌出影响下采动煤体蠕变失稳研究
- 提升煤矿装载效率的可控箕斗定量装载设备设计
- 水分调控下烟煤瓦斯吸附特性对比研究
- 重介质悬浮液密度控制硬件设计与选型探讨
- 坚硬顶板巷道支护参数设计:现场测试与数值分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)