首页 > 代码库 > 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集训笔记【更新中】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。