Learn how prefix sum arrays pre-compute cumulative totals to answer range sum queries in instant O(1) constant time.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
Suppose you need to calculate the sum of array elements from index $L$ to $R$ thousands of times. A loop takes $O(N)$ per query. A Prefix Sum Array pre-computes cumulative totals in $O(N)$ once, answering every subsequent query in $O(1)$ instant time!
$$ ext[i] = ext[i - 1] + ext[i - 1]$$ $$ ext(L dots R) = ext[R + 1] - ext[L]$$
class PrefixSum {
constructor(nums) {
this.prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
this.prefix[i + 1] = this.prefix[i] + nums[i];
}
}
queryRange(left, right) {
// Returns sum of elements from index left to right inclusive in O(1)
return this.prefix[right + 1] - this.prefix[left];
}
}
const tracker = new PrefixSum([3, 1, 4, 1, 5, 9, 2]);
// Prefix array: [0, 3, 4, 8, 9, 14, 23, 25]
console.log(tracker.queryRange(1, 4)); // Elements [1, 4, 1, 5] -> Output: 11
console.log(tracker.queryRange(0, 2)); // Elements [3, 1, 4] -> Output: 8
Find the total number of continuous subarrays whose sum equals k in $O(N)$ time:
function subarraySum(nums, k) {
const prefixCount = new Map([[0, 1]]);
let currentSum = 0;
let totalCount = 0;
for (const num of nums) {
currentSum += num;
if (prefixCount.has(currentSum - k)) {
totalCount += prefixCount.get(currentSum - k);
}
prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
}
return totalCount;
}
console.log(subarraySum([1, 1, 1], 2)); // Output: 2
left === 0 special casing. Allocating size $N + 1$ with prefix[0] = 0 eliminates boundary edge cases cleanly!Use prefix sums for range queries and subarray sum problems. Next, let's explore Recursion and Call Stack Frames!