The Prefix Sum Template in Python, Java and TypeScript

Build the n + 1 totals in one loop, then answer each range with p[j + 1] − p[i].

The prefix sum template is one loop that builds n + 1 running totals and one function that reads a range from two of them. Two lines change between problems, and the highlighted lines mark them: the value accumulated, which can be a count or a flag instead of a number, and the read. Each listing builds the prefix array of 2 6 1 4 3, reads three ranges, and adds three readings of 2,000,000,000.

The prefix sum template in three languages

prefix_sum.pypy

def build_prefix(values: list[int]) -> list[int]:
    prefix = [0] * (len(values) + 1)
    for i, value in enumerate(values):
        prefix[i + 1] = prefix[i] + value
    return prefix


def range_sum(prefix: list[int], i: int, j: int) -> int:
    return prefix[j + 1] - prefix[i]


values = [2, 6, 1, 4, 3]
prefix = build_prefix(values)
print(f"values {values} prefix {prefix}")
for i, j in [(1, 3), (0, 4), (2, 2)]:
    print(f"sum of indices {i} to {j}: {range_sum(prefix, i, j)}")
large = build_prefix([2_000_000_000] * 3)
print(f"three readings of 2000000000: total {range_sum(large, 0, 2)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

values [2, 6, 1, 4, 3] prefix [0, 2, 8, 9, 13, 16]
sum of indices 1 to 3: 11
sum of indices 0 to 4: 16
sum of indices 2 to 2: 1
three readings of 2000000000: total 6000000000

PrefixSum.javajava

import java.util.Arrays;

public class PrefixSum {
    static long[] buildPrefix(int[] values) {
        long[] prefix = new long[values.length + 1];
        for (int i = 0; i < values.length; i++) {
            prefix[i + 1] = prefix[i] + values[i];
        }
        return prefix;
    }

    static long rangeSum(long[] prefix, int i, int j) {
        return prefix[j + 1] - prefix[i];
    }

    public static void main(String[] args) {
        int[] values = {2, 6, 1, 4, 3};
        long[] prefix = buildPrefix(values);
        System.out.println("values " + Arrays.toString(values) + " prefix " + Arrays.toString(prefix));
        int[][] ranges = {{1, 3}, {0, 4}, {2, 2}};
        for (int[] range : ranges) {
            System.out.println("sum of indices " + range[0] + " to " + range[1] + ": " + rangeSum(prefix, range[0], range[1]));
        }
        long[] large = buildPrefix(new int[] {2_000_000_000, 2_000_000_000, 2_000_000_000});
        System.out.println("three readings of 2000000000: total " + rangeSum(large, 0, 2));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

values [2, 6, 1, 4, 3] prefix [0, 2, 8, 9, 13, 16]
sum of indices 1 to 3: 11
sum of indices 0 to 4: 16
sum of indices 2 to 2: 1
three readings of 2000000000: total 6000000000

prefix_sum.tsts

function buildPrefix(values: number[]): number[] {
  const prefix: number[] = new Array(values.length + 1).fill(0);
  for (let i = 0; i < values.length; i++) {
    prefix[i + 1] = prefix[i] + values[i];
  }
  return prefix;
}

function rangeSum(prefix: number[], i: number, j: number): number {
  return prefix[j + 1] - prefix[i];
}

const values = [2, 6, 1, 4, 3];
const prefix = buildPrefix(values);
console.log(`values [${values.join(", ")}] prefix [${prefix.join(", ")}]`);
for (const [i, j] of [[1, 3], [0, 4], [2, 2]]) {
  console.log(`sum of indices ${i} to ${j}: ${rangeSum(prefix, i, j)}`);
}
const large = buildPrefix([2_000_000_000, 2_000_000_000, 2_000_000_000]);
console.log(`three readings of 2000000000: total ${rangeSum(large, 0, 2)}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

values [2, 6, 1, 4, 3] prefix [0, 2, 8, 9, 13, 16]
sum of indices 1 to 3: 11
sum of indices 0 to 4: 16
sum of indices 2 to 2: 1
three readings of 2000000000: total 6000000000

The three listings print the same totals. Building is O(n) time and O(n) extra space for n values, and each read is O(1).

The large total is where the languages part. A Java int holds at most 2³¹ − 1, about 2.1 × 10⁹, so the Java listing stores the totals as long; with int[], a total past that limit wraps round to a negative number with no error. A TypeScript number holds every integer exactly up to 2⁵³, about 9 × 10¹⁵, and rounds beyond it. Python's integers have no limit.

← → move through sections and cards