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

segment interval range
104

原文：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) 空间