Range Queries
Prefix Sums and Range Queries
Written by Swapnil RajaPublished
If a problem asks the same question about many different ranges, precompute once rather than re-scanning for every query.
Prefix sums
Build an array where each entry holds the total of everything before it. The sum of any range is then the difference of two entries - one subtraction, regardless of how wide the range is.
O(1) range sums after O(n) setup
javascript
function buildPrefix(items) {
const prefix = new Array(items.length + 1).fill(0)
for (let i = 0; i < items.length; i++) {
prefix[i + 1] = prefix[i] + items[i]
}
return prefix
}
// Sum of items[from..to], inclusive.
function rangeSum(prefix, from, to) {
return prefix[to + 1] - prefix[from]
}
const items = [3, 1, 4, 1, 5, 9, 2, 6]
const prefix = buildPrefix(items)
console.log(rangeSum(prefix, 2, 5)) // 19
console.log(rangeSum(prefix, 0, 7)) // 31