线段树

发表于 | 分类于 | 浏览 次

什么是线段树，如何实现线段树，线段树用在哪些场景？

  • 线段树结构
    • 线段树每个节点存储了一个区间上的元素之和．
  • 线段树可以做什么？
    • 线段树可以在线维护以及查询区间上的最值，求和．
    • 可以扩展到二维线段树（矩阵树）和三维线段树（空间树）
    • 对于一维线段树来说，每次更新以及查询的时间复杂度为O(logn)
  • 线段树中存储树结构所需要的空间大小
    • 无优化的线段树需要2*2k（2k-1<n<2k）空间,一般会开到4*n的空间防止RE

Count of Smaller Numbers After Self

建立一个线段树，每个节点表示在某个范围内的元素的个数．

参考文献

[1] https://www.cnblogs.com/xenny/p/9801703.html
[2] 线段树详解: https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/