StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A skip list can do insertion/removal/index lookup each in <code>O(log n)</code>: <a href="http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist" rel="nofollow">http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist</a></p> <p>For the <code>O(n^1/2)</code> insert/remove and <code>O(1)</code> index, I assume something a bit like a C++ <code>deque</code>, but consisting of <code>n^1/2</code> contiguous blocks, each of <code>n^1/2</code> elements (+/-1 on each square root, of course). To remove, you have to shuffle down part of the block containing the removed element (<code>O(n^1/2)</code>), and then shuffle down the <em>whole</em> of the higher blocks, which you'd do by adjusting an offset for each block (at most <code>O(n^1/2)</code> blocks) rather than actually moving anything. To insert, you may have to reallocate a block (<code>O(n^1/2)</code>) and adjust offsets. In both cases, you may also have to shift one or two elements off the start/end of some blocks to the end/start of the previous/next block, again at most <code>O(n^1/2)</code> times, to maintain an invariant that no two blocks differ in size by more than 1, except for the last which is used to take up slack. Finally, you sometimes have to create or destroy a block. Lookup is <code>O(1)</code> because you can get to within one block of the element you're looking for with a single division, then consult the stored offsets for one or two blocks to actually find it.</p> <p>Don't know what that's called, though, or whether I've missed some important detail that means it doesn't work as I've described it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload