327. 区间和的个数
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1： 输入：nums = [-2,5,-1], lower = -2, upper = 2 输出：3 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
/**
* @param {number[]} nums
* @param {number} lower
* @param {number} upper
* @return {number}
*/
var countRangeSum = function (nums, lower, upper) {
let n = nums.length, pre = [0]
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i]
let tmp = Array(n).fill(0), res = 0
const merge_sort = (l, r) => {
if (l == r) return
let mid = l + r >> 1
merge_sort(l, mid)
merge_sort(mid + 1, r)
let k1 = k2 = l
for (let j = mid + 1; j <= r; j++) {
while (k1 <= mid && pre[j] - upper > pre[k1]) k1++
while (k2 <= mid && pre[j] - lower >= pre[k2]) k2++
res += k2 - k1
}
let p1 = l, p2 = mid + 1, k = l
while (p1 <= mid || p2 <= r) {
if (p2 > r || p1 <= mid && pre[p1] <= pre[p2]) {
tmp[k++] = pre[p1++]
} else {
tmp[k++] = pre[p2++]
}
}
for (let i = l; i <= r; i++) pre[i] = tmp[i]
}
merge_sort(0, n)
return res
};