Easy · Segment Tree
Understand → Visualise → Practice.
Return the maximum value in each inclusive immutable-array range query.
A segment tree stores the maximum of every block of a recursive halving, so any range is covered by O(log n) stored blocks.
Put the values in the leaves and set each parent to the max of its two children.
Move the two boundaries upward; whenever a boundary node is not shared with the inside, take its value and step inward.
The answer is the max of the collected blocks.
O(n) to build and O(log n) per query, with O(n) space.
Max is not invertible, so prefix arrays cannot answer it; you need stored blocks.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.