算法笔记 - 线段树

2018-12-24 本文已影响0人袁旭程

线段树的实现比较简单
时间复杂度 O(nlogn)
传统线段树一般用递归实现
线段树可以实现区间数值修改O(logn)复杂度。而且是lazy eval, 在需要的时候才会更新
线段树的主要思想是分治，和分治算法的实现非常像
线段树可以和其他的一些树混合使用，叫做树套树，比如混合线段树和平衡树
直接的线段树很少会直接考，都会变着形来出题
注意，如果使用数组来实现树节点，需要4n大小的数组

上一篇下一篇

猜你喜欢

热点阅读