Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

adamant's blog

By adamant, 10 years ago, translation, In English

Hi everyone!

I recently read about such an interesting data structure as skip-list. It seemed to me, the structure is very interesting and at the same time easy to use. That is the reason I decided to experiment with the structure in various problems and try to implement the various modifications of it. "Basic" operations are well described in this entry from wikipedia. So I will not give them too much time.

Basic implementation.

Here is "pure" variant of skip-list — implemented only the basic operations — find, insert, erase.

code

Adding order statistics functions.

Now we need to add two new functions find_by_order() and order_of_key(). In order to do this, in balanced binary trees we used to store the size of subtrees. But here we just should store the length of links. After this both functions can be implemented easy enough. In first function we change binary predicate and comparing not elements themselves, but length of the prefixes they are ending in. In the second function we do everything just like in usual find(), but we also store the length of prefix that lead to current element.

code

Make the structure use implicit key.

When we added find_by_order() we also got an opportunity to make skip-list use implicit key, i.e. key=order of element in set. Everything we need in order to use it is using find_by_order() instead of find().

code

P.S. What do you think about this data structure? How wise is it to use skip-lists on the contests? What other modifications do you know? Also, my implementation is pretty weak, do you know the better one?

  • Vote: I like it
  • +85
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

It was very interested with me too. But now, it is not. I realized it's a weak data structure. I can't upgrade it for more advanced features. Now I used to use AVL or Splay tree, they are more powerful, they can support operators in segment trees (e.g. lazy update).

P/S: This is my implementation for "auto-balanced dynamic-allocation segment tree" (Segment tree + AVL) http://codeforces.com/blog/entry/12285