Range Sums in a Window — Solution & Editorial

Back to the Problem

A subarray (q, p] qualifies iff prefix[p] − prefix[q] ∈ [LO, HI], i.e. prefix[q] ∈ [prefix[p]−HI, prefix[p]−LO]. Sweep prefixes counting predecessors in that window with a BIT over compressed prefix values (or merge-sort recursion). A balanced-list insertion also passes at these limits.

Complexity: O(N log N)