Prefix Sum: Range Query Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Prefix Sum: Complete Guide with Range Query Examples

If you have not read the concept guide yet, start there for the intuition and the complexity analysis. This page gives you the code you can memorize and adapt in an interview. Every template below builds in

O(N)

time and answers queries in

O(1)

time afterward, unless a variation says otherwise.

Main Template: Prefix Sum Array

The core version precomputes a running total so any subarray sum is a single subtraction. This is the class behind Range Sum Query - Immutable, and it works whenever the input array does not change between queries.

Use this for Range Sum Query - Immutable and as the foundation for every other variation.

class PrefixSum {
    constructor(nums) {
        // prefix[i] holds the sum of the first i elements.
        // The leading 0 lets a query starting at index 0
        // subtract a real value instead of needing a branch.
        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];
        }
    }

    rangeSum(left, right) {
        // Everything up to and including right, minus
        // everything before left, isolates nums[left..right].
        return this.prefix[right + 1] - this.prefix[left];
    }
}

class PrefixSum:
    def __init__(self, nums: List[int]):
        # One extra slot at the front makes prefix[0] = 0,
        # so a query from index 0 is an ordinary subtraction.
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def range_sum(self, left: int, right: int) -> int:
        # Keep the part after left, drop everything before it.
        return self.prefix[right + 1] - self.prefix[left]

class PrefixSum {
    private long[] prefix;

    // long instead of int: cumulative sums overflow int quickly.
    public PrefixSum(int[] nums) {
        prefix = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public long rangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

type PrefixSum struct {
    prefix []int64
}

func NewPrefixSum(nums []int) *PrefixSum {
    // int64 holds cumulative sums that would wrap int32.
    prefix := make([]int64, len(nums)+1)
    for i, num := range nums {
        prefix[i+1] = prefix[i] + int64(num)
    }
    return &PrefixSum{prefix: prefix}
}

// RangeSum returns the sum of nums[left..right] inclusive.
func (p *PrefixSum) RangeSum(left, right int) int64 {
    return p.prefix[right+1] - p.prefix[left]
}

class PrefixSum
    def initialize(nums)
        # The starting 0 means a query at left = 0 is
        # still a plain subtraction with no branch.
        @prefix = [0]
        nums.each do |num|
            @prefix << @prefix.last + num
        end
    end

    def range_sum(left, right)
        @prefix[right + 1] - @prefix[left]
    end
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

prefix: the precomputed array, always one element longer than nums. Entry prefix[i] holds the sum of the first i input elements. That single convention drives every other line.
nums.length + 1 (or equivalent): the size of the prefix array. The extra slot holds the empty-prefix sum of 0 and keeps prefix[right + 1] in bounds when right is the last index.

Visual Mechanism

    graph TD
    A["Input: nums = [3, 1, 4, 2, 5]"] --> B["prefix[0] = 0"]
    B --> C["prefix[1] = prefix[0] + 3 = 3"]
    C --> D["prefix[2] = prefix[1] + 1 = 4"]
    D --> E["prefix[3] = prefix[2] + 4 = 8"]
    E --> F["prefix[4] = prefix[3] + 2 = 10"]
    F --> G["prefix[5] = prefix[4] + 5 = 15"]
    G --> H["rangeSum(2, 4) = prefix[5] - prefix[2] = 15 - 4 = 11"]

Critical Sections

The build loop reads one element per step and writes the running total one slot ahead. prefix[i] always stores the total of nums[0..i-1], so the first element lands at index 1 and index 0 stays as the neutral 0. If you size the array as n + 1, you never have to special-case a query that starts at index 0.

The query is a single subtraction because prefix[right + 1] includes everything through right, and subtracting prefix[left] removes everything before left. The length of the range never appears in the formula, which is why the query cost does not depend on the range size.

Variations

1. In-place running sum

When the task only wants the transformed array (like LeetCode 1480 Running Sum) and never asks for a subarray query afterward, you can overwrite nums and save the extra

O(N)

space. The old values are never needed again, so the destruction is safe.

function runningSum(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

This trades memory for a loss of flexibility. Once you overwrite nums[i], the original value is gone, so you can no longer answer arbitrary range queries. Use it only when the problem is satisfied with the transformed array itself.

2. Hashmap counting (subarray sum equals k)

When the question is “how many subarrays sum to K”, no single prefix entry answers it. You store every prefix sum you have seen in a hashmap keyed by value, and for each new prefix you ask how many earlier prefixes equal prefix - K. The 0: 1 seed counts subarrays that start at index 0.

Use this for Subarray Sum Equals K .

function subarraySum(nums, k) {
    const seen = new Map();
    seen.set(0, 1); // empty prefix counts once
    let total = 0;
    let result = 0;

    for (const num of nums) {
        total += num;
        // An earlier prefix of total - k means the subarray
        // between that prefix and here sums to exactly k.
        result += seen.get(total - k) || 0;
        seen.set(total, (seen.get(total) || 0) + 1);
    }
    return result;
}

def subarray_sum(nums: List[int], k: int) -> int:
    seen = {0: 1}
    total = 0
    result = 0
    for num in nums:
        total += num
        # If total - k appeared earlier, the subarray between
        # that prefix and here is exactly the one we count.
        result += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return result

Time is

O(N)

, and the map holds at most one entry per distinct prefix sum, so space is

O(N)

. This variant is the one that shows up in Subarray Sum Equals K and Subarray Sums Divisible by K.

3. 2D prefix array (grids)

The same idea extends to matrices. A prefix cell at (i+1, j+1) stores the sum of the whole submatrix from (0,0) to (i,j). A submatrix query is then inclusion-exclusion over four corners: take the big rectangle, subtract the strip above, subtract the strip to the left, and add back the corner region that was subtracted twice.

Use this for Range Sum Query 2D - Immutable .

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        h, w = len(matrix), len(matrix[0])
        # prefix has one extra row and column so the top-left
        # corner of any query stays inside the array.
        self.prefix = [[0] * (w + 1) for _ in range(h + 1)]
        for i in range(h):
            for j in range(w):
                self.prefix[i+1][j+1] = (matrix[i][j]
                    + self.prefix[i][j+1]
                    + self.prefix[i+1][j]
                    - self.prefix[i][j])

    def sum_region(self, r1, c1, r2, c2):
        # Big rectangle minus the above strip and the left
        # strip, then re-add the corner removed twice.
        return (self.prefix[r2+1][c2+1]
            - self.prefix[r1][c2+1]
            - self.prefix[r2+1][c1]
            + self.prefix[r1][c1])

class NumMatrix {
    constructor(matrix) {
        const h = matrix.length, w = matrix[0].length;
        // One extra row and column keep query corners in bounds.
        this.prefix = Array.from({ length: h + 1 }, () => new Array(w + 1).fill(0));
        for (let i = 0; i < h; i++) {
            for (let j = 0; j < w; j++) {
                this.prefix[i + 1][j + 1] = matrix[i][j]
                    + this.prefix[i][j + 1]
                    + this.prefix[i + 1][j]
                    - this.prefix[i][j];
            }
        }
    }

    sumRegion(r1, c1, r2, c2) {
        return this.prefix[r2 + 1][c2 + 1]
            - this.prefix[r1][c2 + 1]
            - this.prefix[r2 + 1][c1]
            + this.prefix[r1][c1];
    }
}

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int h = matrix.length, w = matrix[0].length;
        prefix = new int[h + 1][w + 1];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                    + prefix[i][j + 1]
                    + prefix[i + 1][j]
                    - prefix[i][j];
            }
        }
    }

    public int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2 + 1][c2 + 1]
            - prefix[r1][c2 + 1]
            - prefix[r2 + 1][c1]
            + prefix[r1][c1];
    }
}

class NumMatrix {
    vector<vector<long long>> prefix;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int h = matrix.size(), w = matrix[0].size();
        prefix.assign(h + 1, vector<long long>(w + 1, 0));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                    + prefix[i][j + 1]
                    + prefix[i + 1][j]
                    - prefix[i][j];
            }
        }
    }

    int sumRegion(int r1, int c1, int r2, int c2) {
        return (int)(prefix[r2 + 1][c2 + 1]
            - prefix[r1][c2 + 1]
            - prefix[r2 + 1][c1]
            + prefix[r1][c1]);
    }
};

type NumMatrix struct {
    prefix [][]int64
}

func NewNumMatrix(matrix [][]int) *NumMatrix {
    h, w := len(matrix), len(matrix[0])
    prefix := make([][]int64, h+1)
    for i := range prefix {
        prefix[i] = make([]int64, w+1)
    }
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            prefix[i+1][j+1] = int64(matrix[i][j])
                + prefix[i][j+1]
                + prefix[i+1][j]
                - prefix[i][j]
        }
    }
    return &NumMatrix{prefix: prefix}
}

func (nm *NumMatrix) SumRegion(r1, c1, r2, c2 int) int64 {
    return nm.prefix[r2+1][c2+1]
        - nm.prefix[r1][c2+1]
        - nm.prefix[r2+1][c1]
        + nm.prefix[r1][c1]
}

class NumMatrix
    def initialize(matrix)
        h = matrix.length
        w = matrix[0].length
        @prefix = Array.new(h + 1) { Array.new(w + 1, 0) }
        (0...h).each do |i|
            (0...w).each do |j|
                @prefix[i + 1][j + 1] = matrix[i][j] +
                    @prefix[i][j + 1] + @prefix[i + 1][j] - @prefix[i][j]
            end
        end
    end

    def sum_region(r1, c1, r2, c2)
        @prefix[r2 + 1][c2 + 1] -
            @prefix[r1][c2 + 1] - @prefix[r2 + 1][c1] + @prefix[r1][c1]
    end
end

Build cost is

O(M*N)

time and space, and each query is

O(1)

4. Difference array (range updates)

When the problem applies many “+val to interval [L, R]” operations and you only read the final array, record +val at L and -val at R+1, then one prefix pass materializes the result. This is the update-side mirror of the prefix sum.

Use this for Corporate Flight Bookings .

function differenceArray(n, updates) {
    const diff = new Array(n + 1).fill(0);
    for (const [left, right, val] of updates) {
        diff[left] += val;
        diff[right + 1] -= val; // cancel the addition one past the end
    }
    const result = new Array(n);
    let run = 0;
    for (let i = 0; i < n; i++) {
        run += diff[i]; // prefix pass turns deltas into values
        result[i] = run;
    }
    return result;
}

def difference_array(n, updates):
    diff = [0] * (n + 1)
    for left, right, val in updates:
        diff[left] += val      # starts adding val at index left
        diff[right + 1] -= val # stops adding val just after right
    result = []
    run = 0
    for i in range(n):
        run += diff[i]         # the running total reconstructs values
        result.append(run)
    return result

public int[] differenceArray(int n, int[][] changes) {
    int[] diff = new int[n + 1];
    for (int[] change : changes) {
        int left = change[0], right = change[1], val = change[2];
        diff[left] += val;
        diff[right + 1] -= val; // stop the addition after right
    }
    int[] result = new int[n];
    int run = 0;
    for (int i = 0; i < n; i++) {
        run += diff[i]; // prefix pass converts deltas to values
        result[i] = run;
    }
    return result;
}

vector<int> differenceArray(int n, vector<vector<int>>& changes) {
    vector<int> diff(n + 1, 0);
    for (auto& change : changes) {
        int left = change[0], right = change[1], val = change[2];
        diff[left] += val;
        diff[right + 1] -= val; // cancel the addition one past the end
    }
    vector<int> result(n);
    int run = 0;
    for (int i = 0; i < n; i++) {
        run += diff[i]; // prefix pass turns deltas into values
        result[i] = run;
    }
    return result;
}

Each update is

O(1)

, and the single prefix pass to materialize the answer is

O(N)

Each variation above is a separate review card in the app. Drill the variations individually so you do not blur the difference between them under pressure.

Now head to the practice problems to apply these templates to real challenges.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .