Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 4:44
Merge Sort Tree, Fractional Cascading, 2D Segment Trees
A merge sort tree stores each node's segment as a sorted list, built bottom-up with std::merge in O(n log n) time and memory, and answers threshold questions such as the smallest value at least x in a range, or how many values fall in a band, with a binary search in each of the O(log n) covering nodes. Fractional cascading stores, for every value, its position in both children, so one search at the root suffices, though on real hardware the extra memory can make it slower. The same nesting gives 2D segment trees (16nm memory) and their compressed form for points.
You will learn
- Build a merge sort tree with std::merge and explain its O(n log n) memory and build time
- Answer 'smallest value >= x in [l, r]' and 'count of values in a band' with binary searches in the covering nodes, in O(log^2 n)
- Explain fractional cascading (one search at the root, stored child positions) and measure whether it pays
- Describe multiset-based updates, the std::lower_bound-on-set trap, 2D segment trees and their memory cost