LeetCode 327 Count of Range Sum - Solution

You use prefix sums + merge sort. Count pairs where prefix[j] - prefix[i] is in [lower, upper].

Here's the trick: range sum from i to j = prefix[j+1] - prefix[i]. You find pairs where this difference is in bounds.

Example: nums = [-2,5,-1]. Prefix = [0,-2,3,2]. You count pairs in [-2,2]: (-2)-0, 2-0, 2-3, etc.

Prefix sum + merge sort. For $n = 10^5$: $O(n \log n)$ time. $O(n)$ space.