Segment Tree

Jon Bentley, 1977

Segment trees (and related interval structures) encode Bentley’s divide-and-conquer spirit for static arrays. Gold highlights visit disjoint nodes that fully cover the query interval; after raising leaf 2 to 9, rose tones walk ancestors as each internal max is patched toward the root.