I am using a TreeMap<Integer, Integer> to represent a sorted list which can have duplicate elements. The key corresponds to an arbitrary value in the list and the mapped value corresponds to the number of occurrences. I am using a sorted list concept because I need to efficiently operate over sublists (log n time) and I am using a TreeMap because Java doesn't have any default sorted list implementation.
However, I noticed that the performance of my algorithm was slower than expected, so after doing some research, it appears that the subMap method takes O(log n + k) time, where n is the size of the map and k is the number of elements within the sub map. For large values of k relative to n, this approaches linear time.
How can I operate over submaps (sublists) in sublinear time; or alternatively, is there a better way I can represent a sorted list in Java?
The motivation behind this question: imagining the tree map as a binary search tree, I'd like to find the first node of some subtree, then use that as the entire tree itself, effectively removing the rest of the tree. Ideally this would only take O(log n) time.