[关闭]
@Junlier 2018-10-28T18:57:46.000000Z 字数 1029 阅读 2021

线段树

知识点总结
阅读体验:https://zybuluo.com/Junlier/note/1283868
校内题单(闲人免入):https://www.cnblogs.com/cjoierljl/p/9683242.html
持续更新。。。
这里不水啊,毕竟也是高二的老选手了。。。
丢个题单:

优化连边

对于区间一起往什么地方连边的问题
考虑用线段树优化
因为可以把线段树中代表一段区间的点看做图中的一个节点
那么这个节点包含的区间都与他连边
让这个节点与需要连的地方连边
复杂度优化成是连边次数,是区间长度

线段树合并

动态开点线段树
合并两棵线段树时
如果当前节点有一棵不存在,直接就是存在的那一个
如果当前节点两棵都存在,合并信息,递归合并左右儿子
新不新开点就是可不可持久化的问题了。。。
具体情况具体分析

线段树分治

把询问按照线段树的方法进行分治

一些套路

难操作可以考虑递归(只是会多一个log)

打法不同的线段树

第一种方法码量短那么一丢丢:不管查询区间的变化,直接往下找,常数也小

  1. //随便kuai的一段代码
  2. void Modify(int now,int L,int R,int le,int ri,int xx)
  3. {
  4. if(L==le&&R==ri){~~~;return;}
  5. Pushdown(now);int mid=(L+R)>>1;
  6. if(ri<=mid)Modify(ls,L,mid,le,ri,~);
  7. if(le>mid) Modify(rs,mid+1,R,le,ri,~);
  8. if(le<=mid&&ri>mid)Modify(ls,L,mid,le,mid,~),Modify(rs,mid+1,R,mid+1,ri,~);
  9. Psuhup(now);
  10. }

第二种方法码量稍长,但容易理解:全部准确判断,特定情况下会好一些

  1. void Modify(int now,int L,int R,int le,int ri,lst xx)
  2. {
  3. if(L==le&&R==ri){~~~;return;}
  4. Pushdown(now);int mid=(L+R)>>1;
  5. if(ri<=mid)Modify(ls,L,mid,le,ri,~);
  6. if(le>mid) Modify(rs,mid+1,R,le,ri,~);
  7. if(le<=mid&&ri>mid)
  8. Modify(ls,L,mid,le,mid,~),Modify(rs,mid+1,R,mid+1,ri,~);
  9. Pushup(now);
  10. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注