tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

Segment Tree


Tangshan No.1 Senior High

线段树 · Segment Tree
TSOIer DeAR 2015/3/17
2015 Tangshan ,Hebei

Segment Tree

线段树 目录页

问题的引入

区间修改与查询

/>给定数列a{1..n},m个修改查询操作,修改为将序列a{l..r}的每个值加delta ,查询为对序列a{l..r}求和,输出和。 · 对于30%的数据,0<n<=100,0<l<=r<=n · 对于60%的数据,0<n<=10000,0<l<=r<=n,答案保证不超过INT_MAX · 对于100%的数据,0<n<=1000000,0<l<=r<=n

1

2

Segment Tree

线段树 目录页

基本操作

线段树
? 建树
– 不断二分区间,深度O(logN)

? 单点修改
– 修改从根到该点路径上的所有点

? 区间查询
– 在线段树上划分为O(logN)个小区间

? 区间修改
– 在线段树上划分为O(logN)个小区间 – 每个小区间打延迟标记

2

Segment Tree

线段树 目录页

延迟标记

延迟标记
? 涉及区间修改时,不能修改所有被影响的区间,而要给划分成的O(logN) 个小区间打上延迟标记,等遍历到它们的时候再进行修改并下传标记。
– 把修改尽量推迟到访问时进行,保证访问和修改都仅对logN个区间操作

? 对于不同的情景,延迟标记的含义不同,自然 struct 中变量的含义,范围 一样不同

3

Segment Tree

线段树 目录页

基本应用之区间修改

数轴染色
在一条数轴上有N个点,分别是1~N。一开始所有的点都被染成黑色。接着 我们进行M次操作,第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后 剩余黑色点的个数。
· 延迟标记 add(x) , 数组a[i]=1 , 当对 [l,r] 染色时 change(1,l,r,-1) · 调用 spread(x) 时,若 sum(x<<1)<0 则 sum(x<<1)=0 · 每次操作后输出 sum(1) , 于是 sumst 函数已经不需要 · 关键是保证任何修改 sum(x) 时保证 sum(x)>=0

4

Segment Tree

线段树 目录页

基本应用之区间修改

USACO 开关灯
YYX家门前的街上有N(2<=N<=100000)盏路灯,在晚上六点之前,这些路灯 全是关着的,六点之后,会有M(2<=m<=100000)个人陆续按下开关,这些开 关可以改变从第i盏灯到第j盏灯的状态,现在YYX想知道,从第x盏灯到第y盏灯中 有多少是亮着的(1<=i,j,x,y<=N)
· add(x) 表示 [l(x),r(x)] 中灯改变状态的次数,spread(x) 中若 add(x) 为 奇数则 sum(x)=r(x)-l(x)+1-sum(x),否则不变 · change(x,l,r,1)

5

Segment Tree

线段树 目录页

问题的引入

NOIP 2012 借教室
在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论, 都需要向学校申请借教室。面对海量租借教室的信息,我们自然希望编程解决这 个问题。我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租 借。共有m份订单,每份订单用三个正整数描述,分别为dj, sj, tj,表示某租借者 需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室 。我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需 要每天提供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考 虑。借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份 订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教 室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至 少一天剩余的教室数量不足dj个。现在我们需要知道,是否会有订单无法完全满 足。如果有,需要通知哪一个申请人修改订单。
6

Segment Tree

线段树 目录页

基本应用之区间最值

· 分析: 由于有先到先得的原则,在线操作,对于每一个读入的借教室申请,在sj到 tj内求剩余的教室最小值。若最小值大于请求值,进行区间修改;若小于,通知 修改订单,程序结束。 · 算法? · 数据范围: 对于 10%的数据,有1 ≤ n, m ≤ 10; 对于 30%的数据,有1 ≤ n, m ≤ 1000; 对于 70%的数据,有1 ≤ n, m ≤ 10^5; 对于 100%的数据,有1 ≤ n, m ≤ 10^6, 0 ≤ ri, dj≤ 10^9, 1 ≤ sj≤ tj≤ n。

7

Segment Tree

线段树 目录页

基本应用之区间最值

线段树维护区间最值
· mins(x) 代表区间 [l(x),r(x)] 的最小值 · add(x) 代表区间 [l(x),r(x)] 整体增减的 延迟标记 · 除 build 函数只需在求 mins(x) 处稍作修 改以外,所有函数都需要大量修改

8

Segment Tree

线段树 目录页

基本应用之区间最值
对比区间求和线段树与区间最值线段树: · 对于整个区间,若每个值都加或减k则最大(小)值也加或减k。 Spread(x) 显示了这一对 mins(x<<1) & mins(x<<1|1) 的修改 · change(x) 由于修改的是区间的最值,所以必须让左右端点完全吻 合,否则都有可能求不出正确解;若 l>mid 即所求区间只可能在 st[x<<1|1] 处完全吻合,则递归二分右区间;同理,对 r<=mid 的 情况操作类似。 而当以上两种情况均不满足即 st[x<<1] & st[x<<1|1] 均与 [l,r] 有 交叉时,递归左右两个区间。在这种情况下要改变传递的参数 l,r ,来使得尽快二分到完全吻合的区间。 注意最后更新 mins(x) !

9

Segment Tree

线段树 目录页

基本应用之区间最值

仿照上面对 change(x) 类似的思想,我们可以得到修改后的 minst(x,l,r) 函数。

10

Segment Tree

线段树 目录页

基本应用之区间最值

HDU I Hate It
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最 高的是多少。这让很多学生很反感。 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟 老师的询问。当然,老师有时候需要更新某位同学的成绩。 在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ), 分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。 第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生 的成绩。 接下来有M行。每一行有一个字符 C (只取‘Q’或‘U’) ,和两个正整数A,B 。当C为‘Q’的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学 生当中,成绩最高的是多少。当C为'U'的时候,表示这是一条更新操作,要求把 ID为A的学生的成绩更改为B
11

Tangshan No.1 Senior High

线段树 · Segment Tree
谢谢大家
TSOIer DeAR 2015/3/17
2015 Tangshan ,Hebei


推荐相关:

农业专业英语词汇

segment 腹节 abdominal wall 腹壁 abducens nerve 外展神经 abducent nerve 外...tree 针叶树 aciculate 针状的 aciculiform 针状的 acid 酸 acid base balance ...


汉语言专业英语术语总表(Chinese-english)

segment consonantal segment the four tones high level high rising low ... a conspectus Sinosinologist family tree comparative linguistics SinoSino-...


胡壮麟《语言学教程》测试题及答案

A. tree B. typewriter C. crash D. bang 3. The function of the ... The phonetic features that occur above the level of the segments are ...


英语签名档

end became a Christmas tree 有些人,想走个性路线想疯了,到头来成了圣诞树...segment the line 对你的思念就像风筝段了线 Return to mou that past once,...


发动机专业英语单词

代替(取代)…‘fir-tree’ fixing:枞树形固定(法) ,枞树形榫齿 serration:榫齿,锯齿 stiffen:拉紧,加强 hollow:空心的 20. 22. 24. 26. 28. 29 segment...


语言学词汇表

tree 谱系树 feature symbol 特征标记 features of meaning 意义特征 finite ...假设 second language acquisition 第二语言习得 segment 切分成分 semantic anomaly...


火电厂英语

tree root 枞树形叶根 fixed carbon 固定碳 flow meter 流量计 flow rate ... generator 发电机 generator transformer 主变 gland segment/packing 汽封片 ...


英语专八人文-最全语言学知识点

b. Design Features(特点): Arbitrariness(任意性-Saussure): shu 和 Tree 都...(言语语音):语音学研究对象,亦叫 segment(音段)/phone(音素);分 consonants(...


jbpm4.4开发指南

[INFO] task-segment: [dependency:tree] [INFO] ----------------------------------------------------------------------...


微机实验

三、实验接线图 图1 四、实验程序框图 五、实验程序清单 CODE SEGMENT ASSUME ...写中断服务段地址 STOSW RET INTREEUP3: CLI ;IR3 中断服务 push ax ;压栈...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com