【OI之路】02数据结构-8线段树

博大精深的线段树

势能线段树

主要考虑线段树的深度以及被操作次数

  1. 开方,loglogx次(次幂/2)
  2. 取模,logx次(被减少的数/2)
  3. 整除,logx次(极差/2)

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

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

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

线段树合并的证明

见典型例题

zkw线段树

还没有去学
统计的力量-线段树全接触-张昆玮
BeiYu
wyfcyx

线段树维护动态直径

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

模板题:「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
转载请注明出处,谢谢!