public int countRangeSum(int[] nums, int lower, int upper) {
if (nums == null || nums.length == 0) {
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
int[] count = new int[1];
mergeSort(sum, 0, sum.length - 1, lower, upper, count);
public void mergeSort(long[] sum, int start, int end, int lower, int upper, int[] count) {
int mid = start + (end - start) / 2;
mergeSort(sum, start, mid, lower, upper, count);
mergeSort(sum, mid + 1, end, lower, upper, count);
merge(sum, start, mid, end, lower, upper, count);
public void merge(long[] sum, int start, int mid, int end, int lower, int upper, int[] count) {
long[] temp = new long[end - start + 1];
for (int left = start; left <= mid; left++) {
while (low <= end && sum[low] - sum[left] < lower) ++low;
while (high <= end && sum[high] - sum[left] <= upper) ++high;
while (right <= end && sum[right] <= sum[left]) temp[tIndex++] = sum[right++];
temp[tIndex++] = sum[left];
temp[tIndex++] = sum[right++];
for (int k = start; k <= end; k++) {
sum[k] = temp[k - start];