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

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