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

博大精深的线段树

势能线段树

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

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

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

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

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

线段树合并的证明

见典型例题

zkw线段树

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

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