Question 81
What is the purpose of path compression in a disjoint-set data structure?
During Find, path compression redirects visited nodes toward the set representative. This flattens the structure and speeds up future operations.
What is the purpose of path compression in a disjoint-set data structure?
During Find, path compression redirects visited nodes toward the set representative. This flattens the structure and speeds up future operations.
What is the amortized time complexity of DSU operations using path compression and union by rank?
The combination of path compression and union by rank gives an amortized inverse-Ackermann bound per operation, which is extremely small for practical input sizes.
Which data structure is commonly used for efficient prefix-sum queries and point updates?
A Fenwick tree stores partial aggregates in an array indexed using the least significant set bit. It supports point updates and prefix-sum queries in O(log n).
Which data structure is commonly used for range queries with flexible associative operations and point updates?
A segment tree stores aggregate information over intervals. It supports point updates and range queries in O(log n) for common associative operations such as sum, minimum, or maximum.
What is the time complexity of building a binary heap from an array using bottom-up heap construction?
Bottom-up construction sifts down internal nodes. Most nodes are near the leaves and move only a small distance, so the sum of work over all nodes is O(n).