Range Sum
rangeSum(i, j) = ผลรวม elements ระหว่าง index i ถึง j (inclusive)
ปัญหา
นับจำนวน range sums ที่อยู่ใน [lower, upper]
ตัวอย่าง
arr = [1, 4, 3], lower = 2, upper = 5 -> output: 3
ตัวอย่างโค้ด
const arr = [1, 4, 3];
const upper = 5;
const lower = 2;
const countRangeSum = (arr = [], lower, upper) => {
const sums = [0];
let res = 0;
let last = 0;
let firstge = value => {
let l = 0, r = sums.length, m;
do {
m = Math.floor((r + l) / 2);
sums[m] < value ? l = m : r = m;
} while (r >= l + 2);
while (r > 0 && sums[r - 1] >= value) {
r -= 1;
}
return r;
};
arr.forEach(num => {
last += num;
res += firstge(last - lower + 1) - firstge(last - upper);
sums.splice(firstge(last), 0, last);
});
return res;
};
console.log(countRangeSum(arr, lower, upper));
ผลลัพธ์
3
คำอธิบาย
ใช้ prefix sums และ binary search (firstge = lower_bound)
สำหรับ prefix sum ปัจจุบัน S, ต้องการ prefix ก่อนหน้า P ที่ lower <= S - P <= upper
-> S - upper <= P <= S - lower
นับจำนวน P ใน sorted array sums ด้วย binary search
Time: O(n log n), Space: O(n)
