线段树-区间树-范围树-二叉索引树

133

原文:https://stackoverflow.com/a/17504505

中英对照:

  • Segment tree 线段树
  • Interval tree 区间树
  • Range tree 范围树
  • Binary indexed tree 二叉索引树

主要用于解决的问题:

  • Segment tree 存储区间,查询哪些区间包含给定的点
  • Interval tree 存储区间,查询哪些区间与给定区间相交,也支持点查询(Segment tree)
  • Range tree 存储点,查询哪些点落在了给定区间
  • Binary indexed tree 存储每个索引的项目数,查询索引 m 和 n 之间有多少个项目

性能(k 是结果数):

  • Segment tree O(n logn) 预处理时间,O(k+logn) 查询,O(n logn) 空间
  • Interval tree O(n logn) 预处理时间,O(k+logn) 查询,O(n) 空间
  • Range tree O(n logn) 预处理时间,O(k+logn) 查询,O(n) 空间
  • Binary indexed tree O(n logn) 预处理时间,O(logn) 查询,O(n) 空间