Prefix Sum

Prefix sum is the first major precomputation pattern. When a system asks many range questions over mostly stable data, you pay one linear build cost so each future range answer is just a subtraction.

Why Prefix Sum Exists

If a dashboard asks for revenue from day 10 to day 90, scanning those days is fine once. If it asks thousands of overlapping range questions, repeated scans waste work. Prefix sums store cumulative totals so each range can be answered from two stored values.

Scenario: Billing Usage Ranges

A SaaS billing page shows usage for arbitrary date ranges: last 7 days, billing month, custom export window, and per-team reporting. If the usage array is stable for the rendered period, prefix sums make these range totals fast and predictable.

Same Pattern in Java, Python, and JavaScript

class PrefixSum {
    private final long[] prefix;

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

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

Field judgmentEngineering Notes

• Use prefix sums for repeated range queries over stable data.
• Prefer a leading zero prefix to simplify boundaries.
• State build time, query time, and memory cost.
• Mention update cost when data changes.
• Prefix ideas generalize to counts, balances, and cumulative constraints.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Build a structure that answers repeated inclusive range-sum queries in O(1).
• Count how many contiguous subarrays sum to k.
• Given daily active-user counts, answer many custom date-range total queries.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class PrefixSum {
    private final long[] prefix;

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

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

import java.util.*;

class SubarraySumK {
    static int count(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int running = 0;
        int answer = 0;
        for (int value : nums) {
            running += value;
            answer += seen.getOrDefault(running - k, 0);
            seen.put(running, seen.getOrDefault(running, 0) + 1);
        }
        return answer;
    }
}

class DailyTotals {
    private final long[] prefix;

    DailyTotals(int[] dailyCounts) {
        prefix = new long[dailyCounts.length + 1];
        for (int day = 0; day < dailyCounts.length; day++) {
            prefix[day + 1] = prefix[day] + dailyCounts[day];
        }
    }

    long totalUsers(int startDay, int endDay) {
        return prefix[endDay + 1] - prefix[startDay];
    }
}

Solved modelWorked Interview Answer

Build a structure that answers repeated inclusive range-sum queries in O(1). A leading zero makes boundaries simple: sum(left, right) = prefix[right + 1] - prefix[left].

class PrefixSum {
    private final long[] prefix;

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

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

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Off-by-one errors in inclusive range queries.
• Forgetting the O(n) memory cost.
• Using simple prefix sums when updates and queries are heavily interleaved.

Execution guardrailQuick-Start Checklist

• Add a leading zero prefix.
• Define whether ranges are inclusive or exclusive.
• Use prefix[right + 1] - prefix[left].
• State build, query, and memory costs.
• Discuss update frequency.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Study subarray sum problems with hash maps.
• Review two-dimensional prefix sums for grids.
• Learn Fenwick trees and segment trees for update-heavy cases later.