我正在寻找似乎非常适合我的项目需求的番石榴TreeRangeMap 。java文档说这是基于（java标准？）TreeMap，它有O（log（n））时间来获取，放置和下一步。
但是 TreeRangeMap 应该是某种范围树实现，根据这个SO question，查询的时间复杂度为 O(k + log(n))，空间为 O(n)，k 是范围大小？有人可以证实这一点吗？
我对TreeRangeMap.subRangeMap()操作的时间复杂度也很感兴趣。它是否具有相同的 O(k + log(n))？
谢谢。
这是一种观点，而不是实际的突变或任何东西。subRangeMap在 O(1) 时间内返回，并且RangeMap它返回O(log n)的每个查询操作都有附加成本 - 也就是说，它的所有操作仍然需要O(log n)，只是具有更高的常数因子。
资料来源：我是“实施它的人”。
我们通常使用 Range 树来查找位于给定区间内的点[x1, x2] and x1 < x2。但是，如果范围树是平衡二叉树（如TreeMap使用红黑树实现的情况），则到x1（或后继）和x2（或前任）的搜索路径具有成本O(log n)。当我们找到它们时，如果有k很多点在这个范围内，我们将不得不使用具有线性成本的树遍历来报告它O(k)。所以总而言之O(k + log(n))。
我对 TreeRangeMap.subRangeMap() 操作的时间复杂度也很感兴趣。它是否具有相同的 O(k + log(n))？
<K,V> subRangeMap(Range<K> subRange)返回此范围图与范围相交的部分的视图balanced-binary search Tree，结果只是另一个. 那为什么不呢？