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