首页 > 代码库 > QDEZ集训笔记【更新中】

QDEZ集训笔记【更新中】

自己的理解

【2016-12-31】

 

【主席树】

http://www.cnblogs.com/candy99/p/6160704.html

就是可持久化线段树,对于每个版本建立一颗线段树,可以查询历史版本
为了节省内存和时间直接使用历史版本的形态,把修改的地方沿途新开节点,其他地方继承历史版本
主席树就是前缀和套线段树,每个前缀和建立一颗线段树,继承上一个历史版本,只是单点修改
区间修改也一样,所有区间修改到的点都要新开节点 标记下放时也要新开
总结:就是把各种操作修改到(包括因为下方标记而修改)的节点新开节点,写法上就是多了新开节点而已,其他一样
主席树的线段树是值域线段树,线段树的形态固定并且维护的信息是出现次数所以是可减的,那么主席树做差就得到了一个区间的值域线段树,可以在线段树上二分求kth

 

【树链剖分】

http://www.cnblogs.com/candy99/p/6172163.html

复杂度:每走一个轻边,size至少一倍(可以想想完全二叉树,那个正好一倍),最多走logn次

完全二叉树才是logn,然后这样树高太小卡不住暴力,所以认为树剖的常数很小

链剖序同时是dfs序,但要注意重链先行 

 一个小性质:除了最后的链,每个区间都是重链的一个前缀

题目

 

后缀数组

题目

 

QDEZ集训笔记【更新中】