Arrays And Strings
Prefix Sum
Build a prefix array once, then answer a selected range sum by subtracting two prefix totals.
O(n) build + O(1) query / O(n) space
query end: 5range sum: -
Index 0
5Index 1L
5Index 2
5Index 3
6Index 4
8Index 5R
11Prefix table
P0
0
P1
0
P2
0
P3
0
P4
0
P5
0
P6
0
Time
O(n) build, O(1) query
Space
O(n)
Step Note
Create prefix[0] = 0 so range sums can subtract two stored totals.
function rangeSum(values: number[], left: number, right: number) {
const prefix = Array(values.length + 1).fill(0)
for (let index = 0; index < values.length; index++) {
prefix[index + 1] = prefix[index] + values[index]
}
return prefix[right + 1] - prefix[left]
}