Definition
- Prefix sum array – an array where each entry holds the cumulative total of all elements up to that index.
- Range query – the sum of elements from index left to right is
prefix[right+1] - prefix[left], computed in O(1). - Leading zero – the prefix array is one longer than the input, with
prefix[0] = 0, which makes the range math clean. - Trade-off – O(n) preprocessing for O(1) per query, turning O(n*q) total cost into O(n+q).
- Immutability assumption – the underlying data must not change between queries; for updates, use a Fenwick tree.
The National Bank of India keeps a running total of a customer's daily deposits, so at the end of each day it writes down the cumulative balance so far. Later, to know how much was deposited between day 3 and day 7, the clerk subtracts the cumulative total up to day 2 from the cumulative total up to day 7. One subtraction gives the answer instantly.
Understanding the Concepts
What is a prefix sum?
A prefix sum array stores at each index the cumulative total of all elements from the beginning up to that index. Once built in O(n) time, it allows any range sum query to be answered in O(1) time using a single subtraction.
At the National Bank of India, Rajesh's daily deposits for a closed month are stored in an array. The statement tool needs to compute the total deposits between any two dates. Instead of re-adding each time, we build a prefix sum once and answer every query with one subtraction.
package com.bank.core;
import java.util.Arrays;
public class PrefixSumDemo {
public static void main(String[] args) {
int[] dailyDeposits = {100, 200, 50, 300, 150};
int[] prefix = buildPrefix(dailyDeposits);
System.out.println("Deposits: " + Arrays.toString(dailyDeposits));
System.out.println("Prefix: " + Arrays.toString(prefix));
System.out.println("Sum [1..3]: " + rangeSum(prefix, 1, 3)); // 200+50+300 = 550
}
static int[] buildPrefix(int[] arr) {
int[] prefix = new int[arr.length + 1];
prefix[0] = 0; // leading zero
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}
static int rangeSum(int[] prefix, int left, int right) {
return prefix[right + 1] - prefix[left];
}
}
Deposits: [100, 200, 50, 300, 150]
Prefix: [0, 100, 300, 350, 650, 800]
Sum [1..3]: 550
Why does the leading zero matter?
The prefix array has length n+1 with prefix[0] = 0. This means prefix[i] is the sum of the first i elements, with prefix[0] being the sum of zero elements. The range formula prefix[right+1] - prefix[left] works cleanly without special-casing the start of the array.
// Without leading zero, you need a special case for left=0:
int sum = (left == 0) ? prefix[right] : prefix[right] - prefix[left - 1];
// With leading zero, no special case needed:
int sum = prefix[right + 1] - prefix[left];
How does the range query work mathematically?
The prefix value at position right+1 is the sum of everything from index 0 to right. The prefix value at position left is the sum of everything from index 0 to left-1. Subtracting cancels the part we do not want and leaves exactly the elements from left to right.
prefix[6] - prefix[2] = sum of all 6 elements - sum of first 2 elements
= (arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+arr[5])
- (arr[0]+arr[1])
= arr[2]+arr[3]+arr[4]+arr[5]
package com.bank.core;
public class RangeQueryExplained {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50, 60};
int[] prefix = {0, 10, 30, 60, 100, 150, 210};
// Sum of arr[2..5] = prefix[6] - prefix[2] = 210 - 30 = 180
System.out.println("Sum [2..5]: " + (prefix[6] - prefix[2]));
// Verify: 30+40+50+60 = 180
System.out.println("Verify: " + (30 + 40 + 50 + 60));
}
}
Sum [2..5]: 180
Verify: 180
What is the performance gain?
Without prefix sums, each range query scans the array from left to right, costing O(n). For q queries, the total cost is O(n*q). With prefix sums, the O(n) build is done once, and each query is O(1), so the total cost is O(n+q).
| Approach | Build | Per Query | q Queries |
|----------|-------|-----------|-----------|
| Naive re-sum | O(1) | O(n) | O(n*q) |
| Prefix sum | O(n) | O(1) | O(n+q) |
package com.bank.core;
public class PerformanceComparison {
public static void main(String[] args) {
int n = 1_000_000;
int q = 100_000;
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i + 1;
// Prefix sum approach
long start = System.nanoTime();
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
long total = 0;
for (int i = 0; i < q; i++) {
total += prefix[n] - prefix[i % n];
}
long elapsed = System.nanoTime() - start;
System.out.println("Prefix sum: " + (elapsed / 1_000_000) + " ms");
}
}
How do you use BigDecimal for money?
For banking calculations, the prefix array uses BigDecimal with add and subtract instead of primitive + and -. This keeps totals exact and avoids floating-point errors on money.
package com.bank.statement;
import java.math.BigDecimal;
import java.util.Arrays;
public class StatementRangeSum {
static BigDecimal[] buildPrefix(BigDecimal[] dailyAmounts) {
BigDecimal[] prefix = new BigDecimal[dailyAmounts.length + 1];
prefix[0] = BigDecimal.ZERO;
for (int i = 0; i < dailyAmounts.length; i++) {
prefix[i + 1] = prefix[i].add(dailyAmounts[i]);
}
return prefix;
}
static BigDecimal rangeSum(BigDecimal[] prefix, int left, int right) {
return prefix[right + 1].subtract(prefix[left]);
}
public static void main(String[] args) {
BigDecimal[] deposits = {
new BigDecimal("15000.50"),
new BigDecimal("25000.75"),
new BigDecimal("10000.00"),
new BigDecimal("50000.25"),
new BigDecimal("30000.00")
};
BigDecimal[] prefix = buildPrefix(deposits);
System.out.println("Deposits: " + Arrays.toString(deposits));
System.out.println("Sum [1..3]: " + rangeSum(prefix, 1, 3));
}
}
Deposits: [15000.50, 25000.75, 10000.00, 50000.25, 30000.00]
Sum [1..3]: 85001.00
What about 2D prefix sums?
Prefix sums extend to two dimensions for submatrix sum queries. The 2D prefix stores cumulative sums over rows and columns, and a submatrix sum uses inclusion-exclusion with four prefix values.
package com.bank.core;
public class PrefixSum2D {
static int[][] buildPrefix2D(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int[][] p = new int[rows + 1][cols + 1];
for (int r = 1; r <= rows; r++) {
for (int c = 1; c <= cols; c++) {
p[r][c] = matrix[r-1][c-1]
+ p[r-1][c] + p[r][c-1] - p[r-1][c-1];
}
}
return p;
}
static int submatrixSum(int[][] p, int r1, int c1, int r2, int c2) {
return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];
}
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] p = buildPrefix2D(matrix);
System.out.println("Submatrix [1,1]->[2,2]: " + submatrixSum(p, 1, 1, 2, 2));
// 5+6+8+9 = 28
}
}
Submatrix [1,1]->[2,2]: 28
When should you NOT use prefix sums?
Prefix sums assume the underlying array does not change between queries. If the array is frequently updated, rebuilding the prefix array costs O(n) per update, which defeats the purpose. For dynamic data, use a Fenwick tree (Binary Indexed Tree) for O(log n) updates and queries, or a segment tree for more complex operations.
// Static data: prefix sum is perfect
// Closed-month statement, historical prices, fixed scores
// Dynamic data: use Fenwick tree instead
// Real-time balance updates, live trading data, streaming counts
What are common mistakes?
The most common mistake is an off-by-one error in the range formula. Without the leading zero, the formula changes and developers mix up inclusive vs exclusive bounds.
// WRONG: forgetting leading zero
int[] prefix = new int[n]; // no leading zero
prefix[0] = arr[0];
for (int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i];
// Range query: sum [left..right]
int sum = prefix[right] - (left > 0 ? prefix[left - 1] : 0); // special case needed!
// CORRECT: with leading zero
int[] prefix = new int[n + 1];
prefix[0] = 0;
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
int sum = prefix[right + 1] - prefix[left]; // clean, no special case
What should a senior engineer know?
- Prefix XOR, prefix count, prefix product. The concept generalizes to any cumulative aggregate that supports an inverse operation. Prefix XOR answers range XOR queries; prefix count answers range frequency queries.
- Immutability is the key assumption. Once the data changes, the prefix array is stale. This is why prefix sums pair well with closed-period data in banking (closed-month statements, historical price series).
- Overflow risk. For large arrays with large values, use
longinstead ofintfor the prefix array to avoid overflow.
Visual Overview
Input: [100, 200, 50, 300, 150]
Index: 0 1 2 3 4
Prefix: [ 0, 100, 300, 350, 650, 800]
Index: 0 1 2 3 4 5
Range sum [1..3] = prefix[4] - prefix[1]
= 650 - 100
= 550 (200 + 50 + 300)
┌─────────────────────────────────────────┐
│ prefix[0] prefix[1] prefix[2] ... │
│ 0 100 300 ... │
│ │ │ │ │
│ │ +100 │ +200 │ +50 │
│ └──────────┘──────────┘ │
└─────────────────────────────────────────┘
Key Takeaway
The prefix sum technique trades a one-time linear build for constant-time range sum queries. I create an array where each entry holds the cumulative total of all elements up to that position, with a deliberate leading zero that makes the range math clean. After that, the sum of any contiguous range is a single subtraction: the prefix value just past the right end minus the prefix value at the left start.
The payoff is dramatic when there are many queries. A naive approach costs O(n) per query, so q queries multiply out to O(n*q). Prefix sums answer every query in O(1) after the single O(n) build, dropping the total cost to O(n+q).
In the statement tool at National Bank of India, I build a BigDecimal prefix array over Rajesh's daily deposits for a closed month, and the tool renders many range totals for charts showing how much was deposited between any two dates. One subtraction per range keeps the screen responsive even when drawing dozens of ranges.
The two senior-level points I always add are that prefix sums assume the data is immutable between queries (for dynamic data, use a Fenwick tree), and that for money the prefix array must use BigDecimal with add and subtract to keep totals exact.
Remember one sentence: build the cumulative totals once in O(n), and every range sum is one O(1) subtraction of two prefix values.
---