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


推荐相关:

语言学重要概念梳理(中英文对照版)

任意性 Arbitratriness:shu 和 Tree 都能表示“树”这一概念;同样的 声音,...2. 音位变体 Allophones:没有区分表义单位作用的音段(segment), E.g: 同样...


复习资料

A.bit—frame----packet—data--segment B.bit—packet—frame—data--...5.生成树算法(Spanning Tree Algorithm) 通过将导致循环连接的端口设置为阻塞状态...


《On Building an Accurate Stereo Matching System on...

我想可能是由于作者来自于企业的 研究院才这么起名的,但说出它的别名大家就都知道了,就是 AD-Census,这是 2011 年 提出来的算法,作者与 SegmentTree 是同...


1000个常用单词中英音与美音的差别

tree cross farm hard start might story saw far sea draw left late run ...segment slave duck instant market degree populate buy raise solve metal ...


全面讲解spm8,教你如何fMRI数据处理_图文

(input window),右侧大窗口为树形结构窗口或 图形窗口(Tree Building Window or...Parameters files 和功能像的 normalize 一样,也选择在 segment 中生成的空间标...


查找最高分和次高分_图文

(tree[0],tree[tree.size()-1]); tree.pop_back(); adjustTree(0); } int size() { return tree.size(); } }; class segmentTree//建立线段树 { ...


计算机网络专业术语

(即网卡) Message P75 消息,或报文 Segment P75 (报文)段 Datagram P75 数据...tree 生成树 redundant packets 冗余数据包 Chapter 5 数据链路层,或链路层 ...


驱动系统

Segment Drive Systems commenced work on its third manufacturing plant in ...Tree plantation and CSR activity was carried out thereafter followed by a ...


noip2015普及组解题报告

{ mx=-INF; } 13 }; 14 struct Segment_Tree { 15 int n; 16 int t[maxn],maxv[maxn],maxr[maxn]; 17 18 void build(int u,int L,int R) {...


常用单词中英音与美音的差别

tree cross farm hard start might story saw far sea draw left late run ...segment slave duck instant market degree populate buy raise solve metal ...

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