What Is a Prefix Sum and Why It Eliminates Repeated Work

Concepts: pyPrefixSum, pyPrecompute

The prefix sum array is conceptually simple. prefix[i] stores the sum of all elements from index 0 up to and including index i-1. That's it. prefix[0] is always 0 (the empty prefix). prefix[1] is arr[0]. prefix[2] is arr[0] + arr[1]. prefix[n] is the sum of the entire array. The '1-indexed' convention (prefix array is length n+1 where n is the original array length) is the version you should memorize because it eliminates off-by-one errors in the range query formula. More on that in a moment. Building the Prefix Array Step by Step Walk through the example with me. arr = [3, 1, 4, 1, 5, 9, 2]. prefix[0] = 0. prefix[1] = 0 + 3 = 3. prefix[2] = 3 + 1 = 4. prefix[3] = 4 + 4 = 8. prefix[4] = 8 + 1 = 9. prefix[5] = 9 + 5 = 14. prefix[6] = 14 + 9 = 23. prefix[7] = 23 + 2 = 25. Each cell adds one