Array / Slice
O(1) access / O(n) insert / O(n)
Contiguous storage with O(1) index access; prefix sums turn range queries into subtraction.
How to recognise it
- Repeated range-sum or range-count queries → prefix sum
- In-place rewrite of an array → read/write indices
- Matrix traversal → direction arrays or layer-by-layer bounds
Go
// Prefix sum: sum of a[l..r] inclusive
func buildPrefix(a []int) []int {
pre := make([]int, len(a)+1)
for i, v := range a {
pre[i+1] = pre[i] + v
}
return pre
}
func rangeSum(pre []int, l, r int) int {
return pre[r+1] - pre[l]
}
// Subarray sum equals k: prefix sum + hash map (LC 560)
func subarraySum(nums []int, k int) int {
count, sum := 0, 0
seen := map[int]int{0: 1}
for _, v := range nums {
sum += v
count += seen[sum-k]
seen[sum]++
}
return count
}
// Difference array: add delta to every a[l..r]
func applyRangeAdds(n int, ops [][3]int) []int { // ops: {l, r, delta}
diff := make([]int, n+1)
for _, op := range ops {
diff[op[0]] += op[2]
diff[op[1]+1] -= op[2]
}
res := make([]int, n)
run := 0
for i := 0; i < n; i++ {
run += diff[i]
res[i] = run
}
return res
}Common variants
- Prefix sum → pre[i+1] = pre[i] + a[i]; sum(l..r) = pre[r+1] - pre[l]
- Prefix sum + hash map → Count subarrays with sum k: look up pre - k seen so far
- Difference array → Many range increments → +1 at l, -1 at r+1, then prefix-sum once
- Go slice aliasing → append may share the backing array; copy before mutating