6 docs tagged with "advance data structures"

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

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

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.

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

Segment Trees are used for efficient range queries.

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.