Count Range Sum Approach

Core idea: range sum $S(i, j) = \text{prefix}[j+1] - \text{prefix}[i]$.

You want to count pairs $(i, j)$ where $\text{lower} \leq \text{prefix}[j+1] - \text{prefix}[i] \leq \text{upper}$.

Rearranging: $\text{prefix}[j+1] - \text{upper} \leq \text{prefix}[i] \leq \text{prefix}[j+1] - \text{lower}$. Algorithm:

$1.$ Compute all prefix sums

$2.$ Coordinate compress prefix values

$3.$ Iterate through prefix sums; for each, query how many previous prefix sums fall in the valid range

$4.$ Add current prefix sum to segment tree You're solving a classic "count inversions" variant using segment tree. Time: $O(n \log n)$. Space: $O(n)$.