Skip lists also have [statistically] sublinear times for insertions and range queries. Both are O(logn). Fenwick trees seem to use much less memory while not b

Skip lists also have [statistically] sublinear times for insertions and range queries. Both are O(logn). Fenwick trees seem to use much less memory while not being quite as general-purpose as skip lists.