Algorithm

The function most-significant bit msb(n) returns the index of the highest 1 bit in the integer n. MSB can be resolved using integer algorithm to find the rank in the array of all the powers of 2.

Splay tree is a balanced search tree that it splays the just touched node. Splay Tree CS166: Data Structures

The data structure x-Fast Trie is a binary trie that The nodes of each layer are stored in Cuckoo hash table. Missing 0 and 1 child pointers are used to store links to siblings.

A y-Fast trie splits nodes into blocks. Each block is a balanced search tree and has 2/w to 2w nodes. The block maximums constitutes an ♯ x-Fast Trie. x-Fast and y-Fast Tries CS166: Data Structures

lcp(m, n) = w - 1 - msb(m xor n) where w is the number of bits in a word, and msb is ♯ Most-Significant Bit.

@miloyip has published a post recently which motioned the Alias Method to generate a discrete random variable in O(1). After some research, I find out that it is a neat and clever algorithm. Following are some notes of my study on it.