LeetCode 327 Count of Range Sum - Why Naive Fails

Checking all $O(n^2)$ subarrays and their sums takes $O(n^2)$. With prefix sums, sum computation is $O(1)$, but still $O(n^2)$ pairs.

Example: $n = 10^5$. Checking all $5 \times 10^9$ subarray pairs is too slow.

Prefix sums + merge sort: count pairs of prefix sums where $lower \le prefix[j] - prefix[i] \le upper$. During merge, both halves are sorted. Two pointers count valid pairs. $O(n \log n)$.