List of Advanced Data Structures
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
This article has the list of 100+ Advanced Data Structures that you must understand to prepare to solve advanced problems and compete in competitions like ICPC, Google Code Jam, Facebook Hacker Cup and many more.
Following is the list of 100+ Advanced Data Structures:

Heap
 Min/ Max Heap
 Binomial Heap
 Fibonacci Heap
 Skew Heap
 Leftist Heap
 Soft Heap
 Pairing Heap
 Shadow Heap
 MinMax heap

 AVL Tree
 Red Black Tree
 AA Tree
 Splay Tree
 2 3 Tree

Bitmask

Lowest Common Ancestor in a Binary Tree

Trie

Range minimum query

Range addition query
 Native approach
 Square root decomposition
 Segment tree
 Fenwick tree
 Sparse table
 Cartesian tree

Finding the number of elements less than a given number in a given range
 Fenwick tree

Number of distinct elements in a index range

Sparse tree

Fractional cascading (binary search)

Longest Common Prefix array (LCP)

Prefix Sum Array

Zipper

Piece table

order statistics tree

Patracia tree

Policy based data structures (C++)

 Using XOR Linked list to implement backward and forward navigation of visited web pages
 Using XOR Linked list to implement Most Recently Used list

Implicit K D tree

KDB tree

R tree

M tree

Range tree

Segment tree
 Segment Tree
 2D Segment Tree
 Lazy propogation in Segment tree
 Persistent segment tree
 Heavy light decomposition in Segment tree

Li Chao tree

Fenwick Tree / Binary Index Tree (BIT)
 Fenwick Tree
 2D Fenwick Tree
 3D Fenwick Tree
 Persistent Fenwick Tree

Quad edge

Winged edge

Anagram Trees

Sqrt Tree

Suffix tree

Ukkonenβs Suffix Tree algorithm

ScapeGoat Tree

Rainbow table

Finger tree

Wavelet tree

 Bloom filter
 LogLog
 HyperLogLog
 MinHash
 Count Min sketch
 Skip list
 Treap
 Quotient filter
 Rapidlyexploring Random Tree (RRT)

Kinetic data structure
 Kinetic heap
 Kinetic sorted list
 Kinetic minimum spanning tree
 Kinetic tournament/ priority queue
Following are some of the ideas behind the Advanced Data Structures:
Segment Tree
Segment Tree is a Data Structure that is used to answer range queries (like Range Minimum Query) efficiently. There are different variants of Segment Tree each of which has used in different applications.
 Segment Tree
 2D Segment Tree
 3D Segment Tree
 Persistent Segment Tree
Interval Tree
Interval Tree is a modification of Binary Search Tree (BST) which is used to solve geometric problems such as find a point or line which is overlapping or enclosed in the rectangle.
Fenwick Tree/ Binary Indexed Tree
Fenwick Tree is similar to Segment Tree and is used to solve range queries. It is based on a different idea and is simpler and has less memory load than Segment Tree. It can be used with an invertible operation only. The variants of Fenwick Tree are:
 Fenwick Tree/ Binary Indexed Tree
 2D Fenwick Tree
 3D Fenwick Tree
 Persistent Fenwick Tree
Cartesian Tree
A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence.
A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity
X and Y fast trie
There are 2 variants:
Xfast trie is a data structure used to store integers from a bounded domain. It is a trie of hash tables and supports successor and predecessor operations in log log U time
Yfast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in Xfast tries, and the leaf nodes point to balanced binary search trees instead of values.