「OI之路」02数据结构-8线段树

博大精深的线段树

很多东西可能是可以自己yy的,但名字能方便交流

基本线段树

例题:JSOI2014 奇怪的计算器

区间查询,复杂度log的证明

假设某一次要同时访问左右两边,后面一定是刚进入就退出的(区间的连续性)
所以说其实只有一次需要同时访问两边,复杂度为深度即log
区间修改同样如此

upd:注意,这并不代表「同时访问左右两边」这部分每次只会执行一次

标记永久化

基础文章

其他势能线段树

主要考虑线段树的深度以及被操作次数,保证复杂度基本就是看这段区间能否预测答案(例如整除时区间内相同就跳出)

  1. 开方,$log_2(log_{2}x)$次(次幂/2),BZOJ3211花神游历各国
  2. 取模,logx次(被减少的数/2)
  3. 向下整除,logx次(区间极差/2)

uoj228基础数据结构练习题则在开方的基础上加入了区间加,注意到数的大小虽然不再单向,方差之类依然是单向的

于是区间相同直接打标记

zkw线段树

统计的力量-线段树全接触-张昆玮
只学了最基础的:堆式编号下,我们是可以直接得到叶子节点的编号的;转化为为开区间就能非递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
namespace ZKW
{
int a[1<<19],M=1<<18;
#define lc x<<1
#define rc x<<1|1
void build(){fd(x,M-1,1) a[x]=max(a[lc],a[rc]);}
void change(int x,int val){x+=M;a[x]=val;while(x>1) x>>=1,a[x]=max(a[lc],a[rc]);}
int ask(int l,int r)
{
l+=M-1,r+=M+1;int ans=0;
while((l^r)!=1)
{
if(!(l&1)) chmax(ans,a[l+1]);
if(r&1) chmax(ans,a[r-1]);
l>>=1;r>>=1;
}return ans;
}
};

李超线段树

比较常见的应用是维护线段单点查询,最早碰到是在bzoj适者

其主要思路就是,记录当前区间内,完全覆盖的线段中交mid最高的那个
然后因为只能和当前层有关,只能标记永久化,当一个线段被淘汰的时候,只需要往一侧下传更新(自行推导具体方向)

修改复杂度,若直线直接log,线段要处理log个区间,故log方;询问就是单点询问log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
namespace SGT//李超树
{
#define lc x<<1
#define rc x<<1|1
#define mid (l+r)/2
inline ll V(pll li,ll x){return li.FR*x+li.SE;}
pll mi[N<<2];bool hav[N<<2];
void insert(pll li,int x=1,int l=0,int r=1e6)
{
if(!hav[x]){mi[x]=li;hav[x]=1;return;}
if(V(li,mid)<V(mi[x],mid)) swap(li,mi[x]);if(l==r) return;
if(V(li,l)<V(mi[x],l)) insert(li,lc,l,mid); else insert(li,rc,mid+1,r);
}
ll ask(ll pos,int x=1,int l=0,int r=1e6)
{
ll ans=V(mi[x],pos);
if(l<r)
{
if(pos<=mid and hav[lc]) chmin(ans,ask(pos,lc,l,mid));
if(pos>mid and hav[rc]) chmin(ans,ask(pos,rc,mid+1,r));
}return ans;
}
};

另外还有一些跟前后缀min/max有关的应用:主要是写出一个solve函数后,有些特殊的solve调用(如访问右孩子的solve,附带的是左孩子的min,这种东西是可以记录下来的,带修的话只会调用log次solve)

「bzoj2957」楼房重建:之前写的题解
jsc2019 H Distinct Integers:题解
码队的跑团历险

最后一定是)))(((这样的,先只考虑计算右括号,然后反过来做即可

这种右括号就是其前缀和从0开始递减(左括号+1右括号-1),于是又变成求递减序列长度了,只不过多了个修改的标记维护

吉老师线段树-弱

要求:区间改min,询问区间max或区间和,选择性支持区间加法、区间乘法、区间开根

做法:记录最大值m1,最大值出现次数cnt,严格次大值m2,区间和sum

1
2
3
if(val>=m1) return;
if(val>m2) {m1=val;update tag,update sum;return;}
递归两侧

注意这里标记的意义是,要将区间内最大值改成我现在的值,这个标记是可以合并的

时间复杂度:做递归的时候,这个节点内不同值个数减少(合并了次大和最大),初始所有节点不同值个数的上界就是复杂度,$O(nlogn)$

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
namespace SGT
{
#define Args int x=1,int l=1,int r=n
#define lc x<<1
#define rc x<<1|1
#define mid (l+r)/2
#define LC lc,l,mid
#define RC rc,mid+1,r
struct Data{int mx,cnt,m2;ll sum;}p[N<<2];bool tag[N<<2];
Data operator + (Data a,Data b)
{
if(a.mx<b.mx) swap(a,b);a.sum+=b.sum;
if(a.mx==b.mx) a.cnt+=b.cnt,chmax(a.m2,b.m2);
else chmax(a.m2,b.mx);return a;
}
void upd(int x,int val){p[x].sum-=1ll*(p[x].mx-val)*p[x].cnt,p[x].mx=val,tag[x]=1;}
void pushdown(int x)
{
if(!tag[x]) return;tag[x]=0;
if(p[lc].mx==p[rc].mx) upd(lc,p[x].mx),upd(rc,p[x].mx);
else upd(p[lc].mx>p[rc].mx?lc:rc,p[x].mx);
}
void build(Args){if(l==r) {int now=qread();p[x]={now,1,0,now};}else build(LC),build(RC),p[x]=p[lc]+p[rc];}
void solve(int fl,int fr,int val,Args)
{
if(val>=p[x].mx) return;
if(fl<=l and r<=fr and val>p[x].m2){upd(x,val);return;}pushdown(x);
if(fl<=mid) solve(fl,fr,val,LC);if(fr>mid) solve(fl,fr,val,RC);p[x]=p[lc]+p[rc];
}
int askmx(int fl,int fr,Args)
{
if(fl<=l and r<=fr) return p[x].mx;pushdown(x);
int ret=0;if(fl<=mid) chmax(ret,askmx(fl,fr,LC));if(fr>mid) chmax(ret,askmx(fl,fr,RC));return ret;
}
ll asksum(int fl,int fr,Args)
{
if(fl<=l and r<=fr) return p[x].sum;pushdown(x);
ll ret=0;if(fl<=mid) ret+=asksum(fl,fr,LC);if(fr>mid) ret+=asksum(fl,fr,RC);return ret;
}
};

猫树

以一道题引入:维护序列,1e6次后面插入,1e7次询问区间最值,强制在线

线段树复杂度主要就是在找分界点和前后缀答案,那现在考虑通过预处理加速这个过程

注意到答案满足结合律,对于每个线段树节点都维护前缀、后缀答案,这个很好维护(nlogn),然后每次询问找到区间第一次在线段树上分开的位置p,把两段合并即可;考虑怎么找p,感受一下p的左右端点都是可以用一些log之类求到的;具体而言,对于一般的二叉堆式编号,p=二进制下l和r的lcp

immortalCO的blog

线段树分治

核心思想:线段树结构把区间分为log段,离线后dfs解决问题,那么回溯的时候我们不需要执行删除,而是执行撤销(回滚),主要是利用这两者区别设计数据结构(经典例子是并查集)

bzoj4025 二分图

经典例题

「CTSC2016」时空旅行(口胡)

题意:维护n个集合,呈以0为根的树状,集合元素为四元组$(x,y,z,c)$,根有一个元素$(0,0,0,c_0)$,每个集合由父亲转移,区别为插入或删除一个元素;m次询问对于某个集合s和横坐标xx,求$min_{i\in s}\ (x_i-xx)^2+c_i$(y和z是来卖萌的)

$|x|,|y|,|z|\le1e6,c\le1e12,n,m\le 5e5$

化化式子发现是个斜率优化,注意地球不能加进去,因为斜率为0;不难发现求dfs序后就是区间插入、删除直线,线段树常用套路把直线作为区间(nlogn个)放进去,而且一开始排好序插入的话斜率就是有序的,然后你发现如果把询问也放进去(单点nlogn个),可以用单调队列维护,故总复杂度nlogn;你发现我们的线段树就是一个不错的离线分治结构

线段树合并

计算一下线段树合并的复杂度,主要就是公共区域
考虑每个叶子,只会被合并一次,此后再经过其祖先不算是他的贡献,那么就是深度也就是log
所以说个人认为这个东西并不是由启发式保证的,而是只会被合并一次,严格和不公共的地方无关

例题:bzoj2212 [Poi2011]Tree Rotations、HNOI永无乡

「TJOI / HEOI2016」排序 (加强):资瓷在线区间求和

可以split线段树,类似求第k大,复杂度和合并一样是log;合并暴力合,求和套个平衡树,$O(nlog^2n)$;然后这里split不想写可以考虑用splay,空间也少个log,splay的有序合并也是log的

线段树维护动态直径

前置知识:直径的一些性质,可以在套路集锦里面找到

模板题:「CEOI2019」动态直径

朴素的做法是log方的,就是线段树统计dfs序区间内直径的两个端点,然后用性质枚举端点保留最大的那个,这样写的话如果要带修需要写个树状数组维护每个点的dis,是log方的

然而是可以log做的,就是用更为友好的欧拉序,众所周知lca是欧拉序区间内dis最小的,但因为我们只是求直径,所以出现不是最小的dis也没有影响(尽可能减少限制条件)

故考虑维护以下信息:$ls[x]=dep_A-2dep_B(dfn_A\le dfnB),rs[x]=dep_D-2dep_C(dfn_C\le dfn_D)$

$ss[x]=dep_X+dep_Y-2dep_Z$ ,然后维护就是组合ls和rs、维护lazy标记,复杂度为 $O(nlogn)$ 且常数相对小,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b1b7.html
转载请注明出处,谢谢!