Where it runs
1. The problem
A monitoring dashboard shows the peak latency (the slowest response time) over any window you pick: the last 5 minutes, the last hour, the whole morning. New samples keep arriving and are written over old ones in a buffer of fixed size (an array whose length never changes). You need the maximum over any range, and you need it fast while the data changes.
Last lesson's Fenwick tree answered range questions while the data kept changing. But it relied on one property: you can get sum[l..r] as query(r) - query(l - 1). Everything rests on subtraction. A maximum has no subtraction. An example: the maximum of the whole array [2, 5, 1, 4] is 5, and the maximum of the first two numbers is also 5. From these two fives you cannot learn the maximum of the last two numbers. It could be any number up to 5. In this array it is 4.
So max, min and gcd (greatest common divisor) over a changing range need a different structure. It stores the finished answer for each range, instead of recovering it by subtraction.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- range sum or query with point updates interleaved
- live leaderboard or running rank while scores change
- count inversions or how many earlier values are larger
- range queries while the data keeps changing
Looks similar, isn't
- Prefix sums
Prefix sums read faster but break on any change. This pays log n to allow updates.
- Difference array
That takes many range updates and one read at the end. Here reads and writes are mixed.
- Sweep line (event counting)
A sweep processes events in sorted order and never looks back. Here queries arrive in any order.
- Binary search (array)
Both halve a range each step. One hunts a value, this one aggregates over a range.
n up to 1e6 with q mixed operations gives O((n + q) log n). Memory is O(n) for a Fenwick tree.
On LeetCode
Problems that update single values and ask for a range maximum, minimum or any other merge that has no subtraction. A segment tree answers both in O(log n), and it can also walk down to the first position that passes a check.
The lesson's class with addition as the combine and 0 as the identity.
Build a range max over the baskets. For each fruit walk down to the leftmost basket that fits, then set that basket to minus infinity.
Index the tree by value. For each number v ask the max over values v minus k to v minus 1, add 1 and store it at v.