You could have invented Fenwick trees

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.