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


推荐相关:

线段树讲解

ACM 算法与程序设计结课论文 关于线段树数据结构的研究线段树(Segment Tree)是一种高级的数据结构,顾名思义,它既是线段也是树, 并且是一棵二叉树。线段树的每个...


划分树 C语言

Segment Tree 线段树 35页 1下载券 划分树(算法总结) 3页 免费... }tree[size*4]; int st[size]; struct Tree//val 是记录划分的每一层的...


[PKU 2777] 线段树(一) {概述 基本操作}

线段树 Segment_tree 网上有人把线段树翻译成 Interval_Tree Interval_Tree 是另外一种数据结构 而且并非二叉树 这个是线段树的标准 E 文翻译 可以看 wikipedia 的...


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

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


计算机网络专业术语

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


Oracle B-tree、位图、全文索引三大索引性能比较及优缺...

(disk) 4943 rows processed 小结:从以上的测试我们可以了解到,B-tree 索引在...segment_name,bytes from user_segments where segment_type='INDEX'; SEGMENT_...


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

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


语言学题目有答案

The phonetic features that occur above the level of the segments are ...(20%) 37. Draw a tree diagram according to the PS rules to show the ...


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) {...


生成树

( segment )一个指定端口(designated port ); 非指定端口(Non-designated ports...通过调整优先级,设置根桥和备份根桥 DS-1(config)#spanning-tree vlan 1 ...

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