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:

• Dynamic Array

• Dynamic Stack

• Fusion Tree

• Hashed Array Tree

• Bit Mask

• Priority Queue

• Heap

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

• Self balancing binary tree:

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

• B Tree

• B+ Tree

• Bitmask

• Adjacency matrix

• Adjacency list

• Lowest Common Ancestor in a Binary Tree

• Union Find

  • Optimizations in Union Find

• Trie

• Range minimum query

  • Native approach
  • Square root decomposition
  • Segment tree
  • Fenwick tree
  • Sparse table
  • Cartesian tree

• 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

• Square Root Decomposition

• Sparse tree

• Sparse table

• Binary lifting in Lowest Common Ancestor

• Fractional cascading (binary search)

• Longest Common Prefix array (LCP)

• Prefix Sum Array

• Rope Data Structure

• Gap buffer

• Split buffer/ 2 stack model

• Zipper

• Piece table

• order statistics tree

• Patracia tree

• Policy based data structures (C++)

• XOR Linked list

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

• Radix tree (compressed trie)

• K dimensional tree

• Implicit K D tree

• KDB tree

• R tree

• M tree

• Range tree

• Interval tree

• Ternary Search Tree

• Cartesian Tree

  • Randomized Cartesian Tree

• Palindromic Tree

  • Longest Palindromic Substring

• 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

• Octree

• Quad Trees

• Quad edge

• Winged edge

• Anagram Trees

• X fast tries

• Y fast tries

• Van Emde Boas Trees

• Sqrt Tree

• Suffix array

• Suffix tree

• Ukkonen’s Suffix Tree algorithm

• ScapeGoat Tree

• Burkhard Keller Tree

• Rainbow table

• Finger tree

• Wavelet tree

• Space Partitioning Tree

  • Binary Space Partitioning Tree

• Probabilistic data structures

  • Bloom filter
    • Applications of Bloom Filter
    • Comparison with Bloom Filter
  • LogLog
  • HyperLogLog
  • MinHash
  • Count Min sketch
  • Skip list
  • Treap
  • Quotient filter
  • Rapidly-exploring 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.

• Cartesian Tree
• Randomized Cartesian Tree/ Treap

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:

• X Fast trie
• Y Fast trie

X-fast 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

Y-fast 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 X-fast tries, and the leaf nodes point to balanced binary search trees instead of values.