算法笔记 - 线段树

  • 线段树的实现比较简单
  • 时间复杂度 O(nlogn)
  • 传统线段树一般用递归实现
  • 线段树可以实现区间数值修改O(logn)复杂度。而且是lazy eval, 在需要的时候才会更新
  • 线段树的主要思想是分治， 和分治算法的实现非常像
  • 线段树可以和其他的一些树混合使用，叫做树套树，比如混合线段树和平衡树
  • 直接的线段树很少会直接考，都会变着形来出题
  • 注意，如果使用数组来实现树节点，需要4n大小的数组
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容