# Find a Maximum-Sum Window in a Sparse Array An integer array is represented by constant-value segments instead of individual elements. Each segment `[start, end, value]` means that every index from `start` through `end`, inclusive, contains `value`. Every index not covered by a segment contains zero. Return the maximum sum of any contiguous subarray of exactly `window_size` elements without expanding the full array. ### Function Signature ```python def max_sparse_window_sum( array_length: int, segments: list[list[int]], window_size: int, ) -> int: ... ``` ### Example ```text Input: array_length = 8 segments = [[1, 3, 4], [6, 7, 1]] window_size = 3 Conceptual array: [0, 4, 4, 4, 0, 0, 1, 1] Output: 12 ``` ### Constraints - `1 <= array_length <= 10^18` - `1 <= window_size <= array_length` - `0 <= len(segments) <= 200_000` - Each segment has three integers `[start, end, value]`. - `0 <= start <= end < array_length` - Segments do not overlap, but they may be unsorted and adjacent. - `-10^9 <= value <= 10^9` ### Clarifications - Array indices are zero-based. - A segment's endpoints are inclusive. - Uncovered indices contribute zero. - The returned sum may be negative only when every legal window has a negative total. - Do not allocate memory proportional to `array_length` or `window_size`. - Do not mutate `segments`. - Defining `array_length` explicitly is a practice assumption that makes the sparse array's finite domain unambiguous. ### Hints - A window's sum changes only when one of its boundaries crosses a segment boundary. - Consider a sweep over compressed breakpoints or an interval-prefix representation. - Be careful about long zero gaps and windows whose boundaries fall inside segments.