Advanced Data Structures

Disjoint Set Union (Union-Find) is an efficient data structure to track the union of disjoint sets.

Segment Trees are used for efficient range queries.

A comprehensive guide to Skip List, a probabilistic data structure that provides O(log n) search, insertion, and deletion.

Fenwick Tree (Binary Indexed Tree) is a more space-efficient data structure for cumulative frequency tables.

A comprehensive guide to Fibonacci Heap - a heap data structure with amortized O(1) insert and merge operations, used in advanced graph algorithms.

A comprehensive guide to Skip List - a probabilistic data structure providing O(log n) search, insert, and delete operations.

A comprehensive guide to Treap - a randomized BST that combines properties of Binary Search Trees and heaps for self-balancing.

Sqrt Decomposition is a technique that splits an array into blocks of size sqrt(n) to answer range queries and updates faster than brute force.

A Persistent Segment Tree keeps every previous version of itself accessible after an update, enabling efficient queries on historical states of an array.

Heavy-Light Decomposition breaks a tree into chains so that path queries and updates can be answered in O(log^2 n) using a Segment Tree.