convert to prefix sum problem: count pairs (i, j) where prefix[j] - prefix[i] is in [lower, upper]. use merge sort to count valid pairs during merging.
during merge, for each left element, find range of right elements where difference is in [lower, upper]. the sorted nature of merge sort makes this efficient with two pointers.
approach
- build prefix sum array
- use merge sort to count valid pairs
- during merge, count pairs with sum in range
- combine counts from left, right, and cross pairs
complexity
O(n log n) time from merge sort. O(n) space for prefix sums and temporary arrays.