DSAhardArrays~45m

The Golden Window

Problem

You are an Anthropic engineer monitoring Claude's training runs. Each training step produces an evaluation score delta — positive when the model improves, negative when it regresses. You need to find the contiguous evaluation window with the maximum cumulative score improvement.

The twist: evaluation scores get retroactively corrected as better baselines become available (point updates), and you need to answer window queries instantly after each correction.

Given an array of score deltas and a list of operations:

("update", i, val): set arr[i] = val
("query", l, r): return the maximum subarray sum within arr[l..r] (must include at least one element)

Return the results of all operations. Updates return null.

Examples

Example 1

Input: ([-50, 25, 25, -50], [("query", 0, 3)])

Output: [50]

The optimal window spans indices 1-2 (values 25+25=50). This crosses the midpoint of the segment tree — requires correctly computing L.max_suf + R.max_pre.

Example 2

Input: ([-50, -10, -20, -100], [("query", 0, 3)])

Output: [-10]

All negative deltas — must return the least negative value (-10). A subarray must contain at least one element, so returning 0 is wrong.

Example 3

Input: ([10, 20, 30, 40], [("query", 0, 3), ("update", 2, -100), ("query", 0, 3)])

Output: [100, null, 40]

Initial best window is entire array (100). After updating index 2 to -100, the best window shifts to just index 3 (40).

Constraints

›1 <= n <= 10^5
›-10^4 <= arr[i] <= 10^4
›At most 10^4 operations

Loading question…