Code Templates

Master the prefix sum family of algorithms with these optimized code templates. Use them as starting points for solving range query, cumulative sum, and range update problems. For a conceptual overview, check out the Prefix Sum Guide.

When to Use Prefix Sums

Prefix sums are your go-to solution for range query and cumulative sum problems where you need to:

Answer multiple range sum queries efficiently (
O(1)
per query after
O(N)
preprocessing)
Calculate running totals or cumulative frequencies
Perform range updates efficiently using difference arrays
Solve problems involving subarray sums, matrix ranges, or temporal aggregations

Key Characteristics:

Preprocess once, query many times - Ideal when query frequency justifies preprocessing cost
O(1)
range queries after
O(N)
setup time
Space efficient - Usually
O(N)
additional space
Immutable data assumption (unless using difference arrays)

Common Applications:

Range sum queries (LeetCode 303, 304)
Subarray sum problems (maximum subarray, subarray sum equals k)
Matrix range queries
Frequency prefix sums for character/string problems
Time-based aggregations (carpooling, meeting rooms)
Difference arrays for range updates (LeetCode 370)

1D Prefix Sum - Range Sum Queries

Use 1D prefix sums when you need to answer multiple range sum queries efficiently on an immutable array. After O(n) preprocessing, each range sum query takes O(1) time. This is ideal for problems like finding subarray sums, checking if ranges sum to targets, or computing cumulative statistics.

When to Use:

Multiple range sum queries on the same array
Subarray sum problems (LeetCode 53, 560, 325)
Cumulative frequency calculations
Converting
O(N^2)
brute force to
O(N)
preprocessing +
O(1)
queries

Key Insight: prefix[i] stores the sum of first i elements, so prefix[right+1] - prefix[left] gives the sum from left to right inclusive.

JavaScript:

class PrefixSum1D {
    constructor(nums) {
        this.prefix = new Array(nums.length + 1).fill(0);
        for (let i = 1; i <= nums.length; i++) {
            this.prefix[i] = this.prefix[i - 1] + nums[i - 1];
        }
    }

    // Get sum from index left to right (inclusive)
    rangeSum(left, right) {
        return this.prefix[right + 1] - this.prefix[left];
    }

    // Get total sum of array
    totalSum() {
        return this.prefix[this.prefix.length - 1];
    }
}

Python:

from typing import List

class PrefixSum1D:
    def __init__(self, nums: List[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            self.prefix[i] = self.prefix[i - 1] + nums[i - 1]

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

    def total_sum(self) -> int:
        return self.prefix[-1]

Java:

public class PrefixSum1D {
    private int[] prefix;

    public PrefixSum1D(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

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

    public int totalSum() {
        return prefix[prefix.length - 1];
    }
}

C++:

#include <vector>

class PrefixSum1D {
private:
    std::vector<long long> prefix;

public:
    PrefixSum1D(const std::vector<int>& nums) {
        prefix.resize(nums.size() + 1, 0);
        for (size_t i = 1; i <= nums.size(); ++i) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

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

    long long total_sum() const {
        return prefix.back();
    }
};

Go:

type PrefixSum1D struct {
	prefix []int64
}

func NewPrefixSum1D(nums []int) *PrefixSum1D {
	prefix := make([]int64, len(nums)+1)
	for i := 1; i <= len(nums); i++ {
		prefix[i] = prefix[i-1] + int64(nums[i-1])
	}
	return &PrefixSum1D{prefix: prefix}
}

func (ps *PrefixSum1D) RangeSum(left, right int) int64 {
	return ps.prefix[right+1] - ps.prefix[left]
}

func (ps *PrefixSum1D) TotalSum() int64 {
	return ps.prefix[len(ps.prefix)-1]
}

Ruby:

class PrefixSum1D
  def initialize(nums)
    @prefix = Array.new(nums.length + 1, 0)
    nums.each_with_index do |num, i|
      @prefix[i + 1] = @prefix[i] + num
    end
  end

  # Get sum from index left to right (inclusive)
  def range_sum(left, right)
    @prefix[right + 1] - @prefix[left]
  end

  # Get total sum of array
  def total_sum
    @prefix.last
  end
end

Code Breakdown

The template relies on three critical components:

The Prefix Array (prefix):
- We initialize an array of size N + 1.
- prefix[0] is always 0. This acts as a dummy value that simplifies calculations (avoiding out-of-bounds checks for the start of the array).
- prefix[i] stores the sum of all elements from the start up to index i-1.
- Visual:
```
  graph TD
    Input[Input: nums] -->|Accumulate| Prefix[Prefix: P]
    Prefix -->|P_i = P_i-1 + nums_i-1| Accumulation[Accumulation Logic]

    P0[P0=0] --> P1[P1]
    N0[nums0] --> P1

    style P0 fill:#aaf,stroke:#333
    style N0 fill:#f9d,stroke:#333
```
Range Query Formula:
- To find the sum of the subarray from left to right:
- Sum = prefix[right + 1] - prefix[left]
- Why right + 1? Because prefix[right + 1] contains the sum of everything up to right.
- Why - prefix[left]? We subtract everything before the left index to isolate the range.
Space vs. Time Trade-off:
- Construction: Costs
  O(N)
  time and space once.
- Queries: Cost
  O(1)
  time infinitely.
- This is perfect for high-read, low-write scenarios.

Difference Array - Range Updates

Use difference arrays when you need to perform multiple range updates efficiently on a mutable array. Each range update takes O(1) time, and the final result can be computed in O(n) time. This is perfect for problems involving bulk updates like carpooling, interval additions, or chronological aggregations.

When to Use:

Multiple range additions to an array (LeetCode 370)
Temporal problems (events with start/end times)
Bulk updates on discrete intervals
Converting
O(N)
updates to
O(1)
preprocessing +
O(N)
final computation

Key Insight: diff[i] represents the change at index i. The final array is computed by taking the running sum: result[i] = result[i-1] + diff[i]. Visual:

  graph LR
    Op[Add +VAL to range L...R]
    Op -->|diff_L += VAL| DL[Diff at L]
    Op -->|diff_R+1 -= VAL| DR[Diff at R+1]

    DL -->|Prefix Sum| Result
    DR -->|Prefix Sum| Result

    style DL fill:#9f9,stroke:#333
    style DR fill:#f99,stroke:#333

JavaScript:

class DifferenceArray {
    constructor(size) {
        this.diff = new Array(size + 1).fill(0);
        this.size = size;
    }

    // Add val to range [left, right] inclusive
    updateRange(left, right, val) {
        this.diff[left] += val;
        if (right + 1 < this.diff.length) {
            this.diff[right + 1] -= val;
        }
    }

    // Get the final array after all updates
    getResult() {
        const result = new Array(this.size).fill(0);
        result[0] = this.diff[0];
        for (let i = 1; i < this.size; i++) {
            result[i] = result[i - 1] + this.diff[i];
        }
        return result;
    }
}

Python:

class DifferenceArray:
    def __init__(self, size: int):
        self.diff = [0] * (size + 1)
        self.size = size

    def update_range(self, left: int, right: int, val: int):
        self.diff[left] += val
        if right + 1 < len(self.diff):
            self.diff[right + 1] -= val

    def get_result(self) -> list:
        result = [0] * self.size
        result[0] = self.diff[0]
        for i in range(1, self.size):
            result[i] = result[i - 1] + self.diff[i]
        return result

Java:

public class DifferenceArray {
    private long[] diff;
    private int size;

    public DifferenceArray(int size) {
        this.size = size;
        this.diff = new long[size + 1];
    }

    public void updateRange(int left, int right, long val) {
        diff[left] += val;
        if (right + 1 < diff.length) {
            diff[right + 1] -= val;
        }
    }

    public long[] getResult() {
        long[] result = new long[size];
        result[0] = diff[0];
        for (int i = 1; i < size; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
}

C++:

#include <vector>

class DifferenceArray {
private:
    std::vector<long long> diff;
    int size;

public:
    DifferenceArray(int size) : size(size), diff(size + 1, 0) {}

    void update_range(int left, int right, long long val) {
        diff[left] += val;
        if (right + 1 < diff.size()) {
            diff[right + 1] -= val;
        }
    }

    std::vector<long long> get_result() const {
        std::vector<long long> result(size, 0);
        result[0] = diff[0];
        for (int i = 1; i < size; ++i) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
};

Go:

type DifferenceArray struct {
	diff []int64
	size int
}

func NewDifferenceArray(size int) *DifferenceArray {
	return &DifferenceArray{
		diff: make([]int64, size+1),
		size: size,
	}
}

func (da *DifferenceArray) UpdateRange(left, right int, val int64) {
	da.diff[left] += val
	if right+1 < len(da.diff) {
		da.diff[right+1] -= val
	}
}

func (da *DifferenceArray) GetResult() []int64 {
	result := make([]int64, da.size)
	result[0] = da.diff[0]
	for i := 1; i < da.size; i++ {
		result[i] = result[i-1] + da.diff[i]
	}
	return result
}

Ruby:

class DifferenceArray
  def initialize(size)
    @diff = Array.new(size + 1, 0)
    @size = size
  end

  # Add val to range [left, right] inclusive
  def update_range(left, right, val)
    @diff[left] += val
    if right + 1 < @diff.length
      @diff[right + 1] -= val
    end
  end

  # Get the final array after all updates
  def get_result
    result = Array.new(@size, 0)
    result[0] = @diff[0]
    (1...@size).each do |i|
      result[i] = result[i - 1] + @diff[i]
    end
    result
  end
end

Next Steps

Now that you have the templates, it’s time to apply them. Head over to the Practice Problems page to solve real LeetCode challenges using these patterns.