Prefix Sum

Subarray sum in O(1) after O(n) setup — the trick behind most subarray problems

Build a prefix array where prefix[i] = sum of arr[0..i-1]. Then any subarray sum from l to r = prefix[r+1] - prefix[l] in O(1). Extend with a hashmap to find subarrays with a target sum.

Language:

Python

All languages — Subarray sum queries

JavaScript

const arr = [2, 4, 6, 8, 10];

const prefix = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
  prefix[i + 1] = prefix[i] + arr[i];
}

const rangeSum = (l, r) => prefix[r + 1] - prefix[l];

console.log(rangeSum(1, 3)); // 18
console.log(rangeSum(0, 4)); // 30

TypeScript

const arr: number[] = [2, 4, 6, 8, 10];

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

const rangeSum = (l: number, r: number): number => prefix[r + 1] - prefix[l];
console.log(rangeSum(1, 3)); // 18

Java

int[] arr = {2, 4, 6, 8, 10};

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}

// rangeSum(l, r) inclusive
System.out.println(prefix[4] - prefix[1]); // 6+8+10... wait
// range_sum(1,3) = prefix[4]-prefix[1] = (2+4+6+8)-(2) = 18 ✓
int rangeSum = prefix[3 + 1] - prefix[1];
System.out.println(rangeSum); // 18

package main
import "fmt"

func main() {
    arr := []int{2, 4, 6, 8, 10}

    prefix := make([]int, len(arr)+1)
    for i, x := range arr {
        prefix[i+1] = prefix[i] + x
    }

    rangeSum := func(l, r int) int {
        return prefix[r+1] - prefix[l]
    }

    fmt.Println(rangeSum(1, 3)) // 18
    fmt.Println(rangeSum(0, 4)) // 30
}

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {2, 4, 6, 8, 10};

    vector<int> prefix(arr.size() + 1, 0);
    for (int i = 0; i < arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }

    auto rangeSum = [&](int l, int r) {
        return prefix[r + 1] - prefix[l];
    };

    cout << rangeSum(1, 3) << endl; // 18
    cout << rangeSum(0, 4) << endl; // 30
}