Builds on Segment Tree and Bottom-Up DFS, which you haven’t finished yet.
Max Segment Tree (Range Maximum Query)
You get an integer array nums and an integer k. Choose some elements of nums, keeping their original order (you may skip any), so that:
- each chosen element is strictly larger than the one chosen before it, and
- it is larger by at most
k.
Return the largest number of elements such a choice can have.
[1,3,4,5,8] goes up by 2, 1, 1 and 3, each at most 3. Adding 15 would need a step of 7.Max Segment Tree
values ➔ max tree over value slots ➔ O(log M) window max and point update| 1 | class SegmentTree: |
| 2 | """Max Segment Tree with Point Updates. |
| 3 | Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half). |
| 4 | Time: O(log M) query & update | Space: O(M), M = number of slots |
| 5 | """ |
| 6 | def __init__(self, size: int) -> None: |
| 7 | self.n = size |
| 8 | self.tree = [0] * (4 * self.n) # Every slot starts at 0: no chain ends there yet |
| 9 | |
| 10 | def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None: |
| 11 | # 1. Default The Range, Then Stop At The Leaf For index: |
| 12 | # The first call omits left/right, so they default here; once left == right only one |
| 13 | # slot is left in the range, and that slot is index, so the leaf's own value is updated. |
| 14 | if right == -1: |
| 15 | right = self.n - 1 # Default: start at the whole range |
| 16 | if left == right: |
| 17 | self.tree[node] = max(self.tree[node], val) # Reached the leaf for index: keep the larger value |
| 18 | return |
| 19 | |
| 20 | # 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up: |
| 21 | # index lies in exactly one half, so only one child is visited; recomputing this node's |
| 22 | # max from both children afterward keeps every ancestor's stored max in sync with the new leaf. |
| 23 | mid = (left + right) // 2 |
| 24 | if index <= mid: |
| 25 | self.update(index, val, 2 * node + 1, left, mid) # Go left |
| 26 | else: |
| 27 | self.update(index, val, 2 * node + 2, mid + 1, right) # Go right |
| 28 | self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) # Recompute on the way up |
| 29 | |
| 30 | def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int: |
| 31 | # 1. Default The Range, Then Resolve Full Overlap Or No Overlap: |
| 32 | # A node fully inside [ql, qr] can answer from its own stored max; a node fully outside |
| 33 | # contributes the neutral value 0, since every stored length is at least 0. |
| 34 | if right == -1: |
| 35 | right = self.n - 1 |
| 36 | if ql <= left and right <= qr: |
| 37 | return self.tree[node] # Fully inside the query: use the stored max |
| 38 | if right < ql or left > qr: |
| 39 | return 0 # Fully outside: 0 is neutral, every stored length is at least 0 |
| 40 | |
| 41 | # 2. Split On Partial Overlap And Combine Both Halves: |
| 42 | # Neither child's range is fully inside or outside, so both are queried and the larger result wins. |
| 43 | mid = (left + right) // 2 # Partial overlap: split into both halves |
| 44 | return max(self.query(ql, qr, 2 * node + 1, left, mid), |
| 45 | self.query(ql, qr, 2 * node + 2, mid + 1, right)) |
| 46 | |
| 47 | |
| 48 | def lengthOfLIS(nums: list[int], k: int) -> int: |
| 49 | """Longest Increasing Subsequence II: a max segment tree over values. |
| 50 | The tree's slot v holds the longest valid chain that ends with value v. |
| 51 | Time: O(N log M), M = max(nums) | Space: O(M) |
| 52 | """ |
| 53 | seg = SegmentTree(max(nums) + 1) |
| 54 | answer = 0 |
| 55 | |
| 56 | # 1. Extend The Longest Chain That Can End At Each Value: |
| 57 | # The chain ending at x extends the longest chain whose last value lies in [x - k, x - 1], |
| 58 | # which the segment tree answers as a single range-max query before x's own slot is updated. |
| 59 | for x in nums: |
| 60 | longest = seg.query(max(x - k, 0), x - 1) + 1 # The value before x lies in [x - k, x - 1] |
| 61 | seg.update(x, longest) |
| 62 | answer = max(answer, longest) |
| 63 | return answer |
update, self.tree[node] equals the largest value stored in the slots left..right that node covers.Node i of self.tree stores the maximum of the slots it covers, so lengthOfLIS keeps at slot v the longest chain that ends with value v and reads the best earlier chain for x as seg.query(max(x - k, 0), x - 1). A maximum over a window is not the difference of two prefix maximums, so a Fenwick tree cannot answer it, but a few whole nodes cover any window. query returns self.tree[node] when the node lies inside the window and 0 when it lies outside. Otherwise it asks both children and keeps the larger answer. At most two nodes per level are only partly covered, so one query visits only a few nodes per level. The trap is the line after the recursive call in update: set self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) on every ancestor of the changed leaf. Without it, each stored maximum above the leaf keeps its old value, and later queries miss the new chain.
See it run
A max segment tree: query, then update
x -longest -answer 0
The column label is the node number. Node 0 covers slots 0 to 7, and the leaves are the nodes for single slots.
reada node that query returns because it lies fully inside the windowwrittena node that update sets or recomputes at this stepoldan ancestor whose maximum is out of date because the recompute line is missing
Slot v of the tree holds the longest chain that ends with value v. All 8 slots start at 0, and k = 2.
Gotcha 1 of 6
- The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistakeelse: self.update(index, val, 2 * node + 2, mid + 1, right)Fixelse: self.update(index, val, 2 * node + 2, mid + 1, right) self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])What happens:
updatechanges the leaf forindex, then returns up the recursion. Each node on the way holds the max of its range. Without the lineself.tree[node] = max(...), those nodes keep their old max. A laterqueryreads a stored node and misses the new length.Example: nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3Mistake: returns 4Fix: returns 5
- The query is a sum, as in Range Sum Query - Mutable (LC 307): each node adds its two children, and no maximum is stored. See Segment Tree
- You only need prefix sums or counts with single-point updates, as in Count of Smaller Numbers After Self (LC 315): no range maximum, minimum or range assignment is involved. See Fenwick Tree
- The window has a fixed size, moves one step at a time, and no value changes, as in Sliding Window Maximum (LC 239): a monotonic deque answers each window in
O(1)time and no tree is needed. See Monotonic Deque
Deep Dive
What slot v holds, and why the window is [x - k, x - 1]
The Segment Tree card teaches the tree itself: nodes, ranges, and the walk down to a leaf. This card adds one change. Each node keeps the maximum of its range instead of the sum.
Slot v of the tree holds the length of the longest valid chain that ends with the value v. A chain is valid when it strictly increases and each step adds at most k. Take nums = [3, 1, 2, 5, 4, 7, 6] and k = 2. There are 8 slots, from 0 to 7.
For a new value x, the chain before it ends with some value p. It needs p < x and x - p <= k. So p lies in [x - k, x - 1], and lengthOfLIS reads the best slot in that window with seg.query(max(x - k, 0), x - 1). The new chain is one longer.
Trace: x = 3 reads slots 1 to 2, finds 0, and writes 1 to slot 3. x = 1 writes 1. x = 2 reads slots 0 to 1, finds 1, and writes 2. x = 5 reads slots 3 to 4, finds 1, and writes 2. x = 4 reads slots 2 to 3, finds 2, and writes 3. x = 7 reads slots 5 to 6, finds 2, and writes 3. x = 6 reads slots 4 to 5, finds 3, and writes 4. The answer is 4.
The window ends at x - 1 and not at x. Slot x holds a chain that already ends with an equal value, and a strictly increasing chain cannot extend it.
Why a node can answer for its whole range
A node that lies fully inside the window returns self.tree[node] without looking at its children. That is correct only when tree[node] is the largest value in its range. This is the card's invariant, and update keeps it true.
update sets the leaf to max(self.tree[node], val). Then, on the way back up, each ancestor is set to max(self.tree[2 * node + 1], self.tree[2 * node + 2]). This line runs on every ancestor of the changed leaf. For x = 2 in the trace, the leaf is tree[9], and the ancestors are tree[4], tree[1] and tree[0]. All three change from 1 to 2.
If the loop of lengthOfLIS then reads slots 2 to 3, node 4 covers exactly that window. A node 4 that still holds 1 would return 1 and not 2, and the chain would be one too short.
A node outside the window returns 0. This is neutral here because every stored length is at least 0, so 0 never wins the max. Values that can be negative need -inf instead.
Why a Fenwick tree does not work here
A Fenwick tree answers a prefix, and a range sum is the difference of two prefixes. A maximum has no such difference. The maximum of slots 5 to 6 cannot be computed from the maximum of slots 0 to 6 and the maximum of slots 0 to 4.
The window matters. In the trace, after 3, 1, 2, 5, 4, slot 4 holds 3. For x = 7, the window is slots 5 to 6, and its maximum is 2, so longest = 3. A prefix maximum over slots 0 to 6 returns 3, so longest would be 4, which is wrong. The value 4 is too far below 7, because 7 - 4 = 3 is larger than k = 2.
A Segment Tree needs no subtraction. It covers any window with a few whole nodes and combines them with max.
Cost
With M = max(nums) + 1 slots, update visits one node per level, so it costs O(log M) time. At most two nodes per level are only partly covered by a query, so query also costs O(log M) time. In the trace, a query visits between 5 and 11 of the 15 nodes in use.
lengthOfLIS makes one query and one update for each of the N values. The total is O(N log M) time and O(M) space. The blueprint allocates 4 * self.n entries because the children 2i + 1 and 2i + 2 leave gaps when n is not a power of two. With 8 slots, 15 entries are used and 32 are allocated.
The same tree can also find the first slot that holds at least a given value, as in Fruits Into Baskets III (LC 3479). Start at node 0. Go to the left child when tree[left child] is at least the needed value, and to the right child otherwise. This takes O(log M) time because the maximum at each node tells which half to enter.
60-Second Pitch
"For each value I need the longest chain that ends in a window of smaller values, and then I change one slot. A prefix maximum cannot answer a window, so I use a max Segment Tree over the value slots. Slot v holds the longest chain that ends with v. For each x, query(max(x - k, 0), x - 1) returns the best earlier chain, and update(x, longest) stores the chain one longer. update recomputes every ancestor of the changed leaf as the larger child, so each node always holds the maximum of its range. A node fully inside the window answers alone, and a node outside returns 0. Both operations are O(log M) time, so the total is O(N log M) time and O(M) space. The two mistakes I check are the missing recompute line and the window end x - 1."
Common Questions
- Why not a Fenwick tree?
A Fenwick tree answers prefixes, and a range answer is the difference of two prefixes. A maximum cannot be subtracted. A Segment Tree covers the window with whole nodes and combines them with
max, so it needs no subtraction.- Why is the window
[x - k, x - 1]and not[x - k, x]? The chain must strictly increase. Slot
xholds a chain that ends with a value equal tox, and it cannot be extended byx. For[2, 2]withk = 1, the answer is 1.- What does the missing recompute line cause?
The leaf holds the new length, but its ancestors keep their old maximum. A later query that fully covers an ancestor returns the old number, so a longer chain is missed.
[4, 2, 1, 4, 3, 4, 5, 8, 15]withk = 3returns 4 and not 5.- What is the cost, and what if the values are large?
Each
updateandquerycosts O(log M) time, withM = max(nums) + 1. The total is O(N log M) time and O(M) space. If the values are too large to be slots, replace them by their ranks among the sorted distinct values. Then the window must be found by rank, with a binary search for the first value at leastx - k.- How does the same tree solve Fruits Into Baskets III (LC 3479)?
Store the basket capacities at the leaves. For each fruit, descend from node 0: go left when the left child's maximum is at least the fruit's size, and right otherwise. Then set that leaf to 0 and recompute its ancestors. Each fruit costs
O(log N)time.
SWE Reasoning
Spot it
- Each element needs the best result among earlier values that lie in a window of the value axis, such as
[x - k, x - 1]. - After the query, one slot changes, and the next query depends on that change.
- The needed answer is a maximum over a window. It is not a sum, so subtracting two prefixes does not work.
- The values are small enough to be slots, or can be ranked first. A plain scan of the window costs O(M) per element and is too slow.
The invariant, step by step
- Slot
vholds the longest valid chain that ends with the valuev. Every slot starts at 0. - A leaf changes only by
max(self.tree[node], val), so it never goes down. - After the leaf changes,
updaterecomputes each ancestor as the larger of its two children. - So
self.tree[node]is the largest value in the slots thatnodecovers, for every node, after everyupdate. queryreturns a stored node when it lies fully inside the window, and0when it lies fully outside. Otherwise it asks both children and keeps the larger answer.- The returned nodes cover the window once, so the result is the largest chain that ends in
[x - k, x - 1]. The new chain is that length plus 1.
Traps
- No recompute after the recursive call. The leaf is right and its ancestors keep old maximums. A node that fully covers the window returns the old number, and chains come out too short.
[4, 2, 1, 4, 3, 4, 5, 8, 15]withk = 3gives 4 and not 5. - Adding the children. A node must hold the best single chain. The sum of two chains is not a chain.
[7, 4, 5, 1, 8, 12, 4, 7]withk = 5gives 6 and not 4. - Window
[x - k, x]. Slotxholds an equal value, and an equal value cannot extend a strictly increasing chain.[2, 2]withk = 1gives 2 and not 1. - A neutral value that wins.
0is safe only because every length is at least 0. For negative values, return-inf. 2 * nentries. Leaves can get an index of2 * nor more, andupdateraises IndexError. Allocate4 * self.n.
Practice
Builds on Segment Tree and Bottom-Up DFS, which you haven’t finished yet.
Max Segment Tree (Range Maximum Query)
You get an integer array nums and an integer k. Choose some elements of nums, keeping their original order (you may skip any), so that:
- each chosen element is strictly larger than the one chosen before it, and
- it is larger by at most
k.
Return the largest number of elements such a choice can have.
[1,3,4,5,8] goes up by 2, 1, 1 and 3, each at most 3. Adding 15 would need a step of 7.Max Segment Tree
values ➔ max tree over value slots ➔ O(log M) window max and point update| 1 | class SegmentTree: |
| 2 | """Max Segment Tree with Point Updates. |
| 3 | Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half). |
| 4 | Time: O(log M) query & update | Space: O(M), M = number of slots |
| 5 | """ |
| 6 | def __init__(self, size: int) -> None: |
| 7 | self.n = size |
| 8 | self.tree = [0] * (4 * self.n) # Every slot starts at 0: no chain ends there yet |
| 9 | |
| 10 | def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None: |
| 11 | # 1. Default The Range, Then Stop At The Leaf For index: |
| 12 | # The first call omits left/right, so they default here; once left == right only one |
| 13 | # slot is left in the range, and that slot is index, so the leaf's own value is updated. |
| 14 | if right == -1: |
| 15 | right = self.n - 1 # Default: start at the whole range |
| 16 | if left == right: |
| 17 | self.tree[node] = max(self.tree[node], val) # Reached the leaf for index: keep the larger value |
| 18 | return |
| 19 | |
| 20 | # 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up: |
| 21 | # index lies in exactly one half, so only one child is visited; recomputing this node's |
| 22 | # max from both children afterward keeps every ancestor's stored max in sync with the new leaf. |
| 23 | mid = (left + right) // 2 |
| 24 | if index <= mid: |
| 25 | self.update(index, val, 2 * node + 1, left, mid) # Go left |
| 26 | else: |
| 27 | self.update(index, val, 2 * node + 2, mid + 1, right) # Go right |
| 28 | self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) # Recompute on the way up |
| 29 | |
| 30 | def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int: |
| 31 | # 1. Default The Range, Then Resolve Full Overlap Or No Overlap: |
| 32 | # A node fully inside [ql, qr] can answer from its own stored max; a node fully outside |
| 33 | # contributes the neutral value 0, since every stored length is at least 0. |
| 34 | if right == -1: |
| 35 | right = self.n - 1 |
| 36 | if ql <= left and right <= qr: |
| 37 | return self.tree[node] # Fully inside the query: use the stored max |
| 38 | if right < ql or left > qr: |
| 39 | return 0 # Fully outside: 0 is neutral, every stored length is at least 0 |
| 40 | |
| 41 | # 2. Split On Partial Overlap And Combine Both Halves: |
| 42 | # Neither child's range is fully inside or outside, so both are queried and the larger result wins. |
| 43 | mid = (left + right) // 2 # Partial overlap: split into both halves |
| 44 | return max(self.query(ql, qr, 2 * node + 1, left, mid), |
| 45 | self.query(ql, qr, 2 * node + 2, mid + 1, right)) |
| 46 | |
| 47 | |
| 48 | def lengthOfLIS(nums: list[int], k: int) -> int: |
| 49 | """Longest Increasing Subsequence II: a max segment tree over values. |
| 50 | The tree's slot v holds the longest valid chain that ends with value v. |
| 51 | Time: O(N log M), M = max(nums) | Space: O(M) |
| 52 | """ |
| 53 | seg = SegmentTree(max(nums) + 1) |
| 54 | answer = 0 |
| 55 | |
| 56 | # 1. Extend The Longest Chain That Can End At Each Value: |
| 57 | # The chain ending at x extends the longest chain whose last value lies in [x - k, x - 1], |
| 58 | # which the segment tree answers as a single range-max query before x's own slot is updated. |
| 59 | for x in nums: |
| 60 | longest = seg.query(max(x - k, 0), x - 1) + 1 # The value before x lies in [x - k, x - 1] |
| 61 | seg.update(x, longest) |
| 62 | answer = max(answer, longest) |
| 63 | return answer |
update, self.tree[node] equals the largest value stored in the slots left..right that node covers.Node i of self.tree stores the maximum of the slots it covers, so lengthOfLIS keeps at slot v the longest chain that ends with value v and reads the best earlier chain for x as seg.query(max(x - k, 0), x - 1). A maximum over a window is not the difference of two prefix maximums, so a Fenwick tree cannot answer it, but a few whole nodes cover any window. query returns self.tree[node] when the node lies inside the window and 0 when it lies outside. Otherwise it asks both children and keeps the larger answer. At most two nodes per level are only partly covered, so one query visits only a few nodes per level. The trap is the line after the recursive call in update: set self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2]) on every ancestor of the changed leaf. Without it, each stored maximum above the leaf keeps its old value, and later queries miss the new chain.
See it run
A max segment tree: query, then update
x -longest -answer 0
The column label is the node number. Node 0 covers slots 0 to 7, and the leaves are the nodes for single slots.
reada node that query returns because it lies fully inside the windowwrittena node that update sets or recomputes at this stepoldan ancestor whose maximum is out of date because the recompute line is missing
Slot v of the tree holds the longest chain that ends with value v. All 8 slots start at 0, and k = 2.
Gotcha 1 of 6
- The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistakeelse: self.update(index, val, 2 * node + 2, mid + 1, right)Fixelse: self.update(index, val, 2 * node + 2, mid + 1, right) self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])What happens:
updatechanges the leaf forindex, then returns up the recursion. Each node on the way holds the max of its range. Without the lineself.tree[node] = max(...), those nodes keep their old max. A laterqueryreads a stored node and misses the new length.Example: nums = [4, 2, 1, 4, 3, 4, 5, 8, 15], k = 3Mistake: returns 4Fix: returns 5
- The query is a sum, as in Range Sum Query - Mutable (LC 307): each node adds its two children, and no maximum is stored. See Segment Tree
- You only need prefix sums or counts with single-point updates, as in Count of Smaller Numbers After Self (LC 315): no range maximum, minimum or range assignment is involved. See Fenwick Tree
- The window has a fixed size, moves one step at a time, and no value changes, as in Sliding Window Maximum (LC 239): a monotonic deque answers each window in
O(1)time and no tree is needed. See Monotonic Deque
Deep Dive
What slot v holds, and why the window is [x - k, x - 1]
The Segment Tree card teaches the tree itself: nodes, ranges, and the walk down to a leaf. This card adds one change. Each node keeps the maximum of its range instead of the sum.
Slot v of the tree holds the length of the longest valid chain that ends with the value v. A chain is valid when it strictly increases and each step adds at most k. Take nums = [3, 1, 2, 5, 4, 7, 6] and k = 2. There are 8 slots, from 0 to 7.
For a new value x, the chain before it ends with some value p. It needs p < x and x - p <= k. So p lies in [x - k, x - 1], and lengthOfLIS reads the best slot in that window with seg.query(max(x - k, 0), x - 1). The new chain is one longer.
Trace: x = 3 reads slots 1 to 2, finds 0, and writes 1 to slot 3. x = 1 writes 1. x = 2 reads slots 0 to 1, finds 1, and writes 2. x = 5 reads slots 3 to 4, finds 1, and writes 2. x = 4 reads slots 2 to 3, finds 2, and writes 3. x = 7 reads slots 5 to 6, finds 2, and writes 3. x = 6 reads slots 4 to 5, finds 3, and writes 4. The answer is 4.
The window ends at x - 1 and not at x. Slot x holds a chain that already ends with an equal value, and a strictly increasing chain cannot extend it.
Why a node can answer for its whole range
A node that lies fully inside the window returns self.tree[node] without looking at its children. That is correct only when tree[node] is the largest value in its range. This is the card's invariant, and update keeps it true.
update sets the leaf to max(self.tree[node], val). Then, on the way back up, each ancestor is set to max(self.tree[2 * node + 1], self.tree[2 * node + 2]). This line runs on every ancestor of the changed leaf. For x = 2 in the trace, the leaf is tree[9], and the ancestors are tree[4], tree[1] and tree[0]. All three change from 1 to 2.
If the loop of lengthOfLIS then reads slots 2 to 3, node 4 covers exactly that window. A node 4 that still holds 1 would return 1 and not 2, and the chain would be one too short.
A node outside the window returns 0. This is neutral here because every stored length is at least 0, so 0 never wins the max. Values that can be negative need -inf instead.
Why a Fenwick tree does not work here
A Fenwick tree answers a prefix, and a range sum is the difference of two prefixes. A maximum has no such difference. The maximum of slots 5 to 6 cannot be computed from the maximum of slots 0 to 6 and the maximum of slots 0 to 4.
The window matters. In the trace, after 3, 1, 2, 5, 4, slot 4 holds 3. For x = 7, the window is slots 5 to 6, and its maximum is 2, so longest = 3. A prefix maximum over slots 0 to 6 returns 3, so longest would be 4, which is wrong. The value 4 is too far below 7, because 7 - 4 = 3 is larger than k = 2.
A Segment Tree needs no subtraction. It covers any window with a few whole nodes and combines them with max.
Cost
With M = max(nums) + 1 slots, update visits one node per level, so it costs O(log M) time. At most two nodes per level are only partly covered by a query, so query also costs O(log M) time. In the trace, a query visits between 5 and 11 of the 15 nodes in use.
lengthOfLIS makes one query and one update for each of the N values. The total is O(N log M) time and O(M) space. The blueprint allocates 4 * self.n entries because the children 2i + 1 and 2i + 2 leave gaps when n is not a power of two. With 8 slots, 15 entries are used and 32 are allocated.
The same tree can also find the first slot that holds at least a given value, as in Fruits Into Baskets III (LC 3479). Start at node 0. Go to the left child when tree[left child] is at least the needed value, and to the right child otherwise. This takes O(log M) time because the maximum at each node tells which half to enter.
60-Second Pitch
"For each value I need the longest chain that ends in a window of smaller values, and then I change one slot. A prefix maximum cannot answer a window, so I use a max Segment Tree over the value slots. Slot v holds the longest chain that ends with v. For each x, query(max(x - k, 0), x - 1) returns the best earlier chain, and update(x, longest) stores the chain one longer. update recomputes every ancestor of the changed leaf as the larger child, so each node always holds the maximum of its range. A node fully inside the window answers alone, and a node outside returns 0. Both operations are O(log M) time, so the total is O(N log M) time and O(M) space. The two mistakes I check are the missing recompute line and the window end x - 1."
Common Questions
- Why not a Fenwick tree?
A Fenwick tree answers prefixes, and a range answer is the difference of two prefixes. A maximum cannot be subtracted. A Segment Tree covers the window with whole nodes and combines them with
max, so it needs no subtraction.- Why is the window
[x - k, x - 1]and not[x - k, x]? The chain must strictly increase. Slot
xholds a chain that ends with a value equal tox, and it cannot be extended byx. For[2, 2]withk = 1, the answer is 1.- What does the missing recompute line cause?
The leaf holds the new length, but its ancestors keep their old maximum. A later query that fully covers an ancestor returns the old number, so a longer chain is missed.
[4, 2, 1, 4, 3, 4, 5, 8, 15]withk = 3returns 4 and not 5.- What is the cost, and what if the values are large?
Each
updateandquerycosts O(log M) time, withM = max(nums) + 1. The total is O(N log M) time and O(M) space. If the values are too large to be slots, replace them by their ranks among the sorted distinct values. Then the window must be found by rank, with a binary search for the first value at leastx - k.- How does the same tree solve Fruits Into Baskets III (LC 3479)?
Store the basket capacities at the leaves. For each fruit, descend from node 0: go left when the left child's maximum is at least the fruit's size, and right otherwise. Then set that leaf to 0 and recompute its ancestors. Each fruit costs
O(log N)time.
SWE Reasoning
Spot it
- Each element needs the best result among earlier values that lie in a window of the value axis, such as
[x - k, x - 1]. - After the query, one slot changes, and the next query depends on that change.
- The needed answer is a maximum over a window. It is not a sum, so subtracting two prefixes does not work.
- The values are small enough to be slots, or can be ranked first. A plain scan of the window costs O(M) per element and is too slow.
The invariant, step by step
- Slot
vholds the longest valid chain that ends with the valuev. Every slot starts at 0. - A leaf changes only by
max(self.tree[node], val), so it never goes down. - After the leaf changes,
updaterecomputes each ancestor as the larger of its two children. - So
self.tree[node]is the largest value in the slots thatnodecovers, for every node, after everyupdate. queryreturns a stored node when it lies fully inside the window, and0when it lies fully outside. Otherwise it asks both children and keeps the larger answer.- The returned nodes cover the window once, so the result is the largest chain that ends in
[x - k, x - 1]. The new chain is that length plus 1.
Traps
- No recompute after the recursive call. The leaf is right and its ancestors keep old maximums. A node that fully covers the window returns the old number, and chains come out too short.
[4, 2, 1, 4, 3, 4, 5, 8, 15]withk = 3gives 4 and not 5. - Adding the children. A node must hold the best single chain. The sum of two chains is not a chain.
[7, 4, 5, 1, 8, 12, 4, 7]withk = 5gives 6 and not 4. - Window
[x - k, x]. Slotxholds an equal value, and an equal value cannot extend a strictly increasing chain.[2, 2]withk = 1gives 2 and not 1. - A neutral value that wins.
0is safe only because every length is at least 0. For negative values, return-inf. 2 * nentries. Leaves can get an index of2 * nor more, andupdateraises IndexError. Allocate4 * self.n.