title: TreeRangeMap time and space complexities
body: <p>I'm looking to guava <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/TreeRangeMap.html" rel="nofollow noreferrer">TreeRangeMap</a> that seem to very well suit my needs for a project. The java docs says that is based on a (java standard ?) TreeMap that have O(log(n)) time for get, put and next. </p>
  
  <p>But the TreeRangeMap should be some kind of range tree implementation that according to this <a href="https://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t">SO question</a> have O(k + log(n)) time complexity for queries, O(n) space, with k being the range size?. Can somebody confirm this?</p>
  
  <p>I'm also very interested in the time complexity of <a href="http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/TreeRangeMap.html#subRangeMap%28com.google.common.collect.Range%29" rel="nofollow noreferrer">TreeRangeMap.subRangeMap()</a> operation. Does it have the same O(k + log(n))?</p>
  
  <p>Thanks.</p>