LeetCode 2407 Longest Increasing Subsequence II - Implementation

class SegmentTree:
    def query(l, r):  // max in range
    def update(i, val):  // point update

tree = SegmentTree(max(nums) + 1)

for num in nums:
    left = max(0, num - k)
    right = num - 1
    maxLen = tree.query(left, right) if left <= right else 0
    tree.update(num, maxLen + 1)

return tree.query(0, max(nums))

Time: $O(n \log m)$ where $m$ is max value. Space: $O(m)$ for tree.