Core idea: prefix sums merge sort. The problem becomes: given prefix sum array“pre”, count pairs“(i, j)” with“i j” and“lower ≤ pre[j] - pre[i] ≤ upper”. During merge, both halves are sorted, so two moving pointers count every valid cross-half pair in one linear pass.class Solution {public int countRangeSum(int[] nums, int lower, int upper) {int n nums.length;long[] pre new long[n 1];for (int i 0; i n; i) pre[i 1] pre[i] nums[i]; // long avoids overflowreturn (int) mergeSort(pre, new long[n 1], 0, n, lower, upper);}private long mergeSort(long[] arr, long[] tmp, int l, int r, int lower, int upper) { if (l r) return 0; int mid l (r - l) / 2; long cnt mergeSort(arr, tmp, l, mid, lower, upper) mergeSort(arr, tmp, mid 1, r, lower, upper); // count cross-half pairs: i in [l, mid], j in [mid1, r] int lo mid 1, hi mid 1; for (int i l; i mid; i) { while (lo r arr[lo] - arr[i] lower) lo; // first j with diff lower while (hi r arr[hi] - arr[i] upper) hi; // first j with diff upper cnt hi - lo; } // merge the two sorted halves int k l, p l, q mid 1; while (p mid q r) tmp[k] arr[p] arr[q] ? arr[p] : arr[q]; while (p mid) tmp[k] arr[p]; while (q r) tmp[k] arr[q]; for (int i l; i r; i) arr[i] tmp[i]; return cnt; }}Key pointsUse“long” for“pre”: prefix sums can reach“n × 2^31”, which overflows“int”.Accumulate the count in“long”: the answer can be up to“n(n1)/2 ≈ 5×10^9”, exceeding“int”.Count before merging, never after. Pointers“lo”/“hi” only move forward, so each level stays linear.Complexity:“O(n log n)” time,“O(n)” space.Alternatives: coordinate-compress prefix sums and use a Fenwick tree (“O(n log n)”, no reordering side effect), or a“TreeMap” of counts walked in sorted order. The merge-sort version is the shortest and has the smallest constant factor — recommended as the primary solution.Verified against brute-force“O(n²)” on 5,000 random cases and all three official samples (“3” /“15” /“4”).