EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Fundamentals
Data Structures & Algorithms

Prefix Sums and Difference Arrays

Turn repeated range work into constant-time queries or constant-time lazy marks by changing what the array stores.

Category Fundamentals
Level basic
Source TeX + C++
preprocessingrange queriesrange updates
Fundamentals

Prefix Sums and Difference Arrays

The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.

Raw TeX

Overview

Prefix sums and difference arrays are among the smallest tools in the toolkit, but they repeatedly remove an entire logarithm or even an entire data structure from the solution. They are often the right answer before segment trees and Fenwick trees enter the conversation.

When to Use It

Use a prefix sum when:

  • the query asks for a range sum, count, or any range quantity expressible as a difference of prefixes,

  • the array is static or only built once,

  • many queries are asked after a preprocessing step.

  • Use a difference array when:

  • many updates add the same value on a whole interval,

  • the final array is only needed after all updates are known,

  • reconstructing once at the end is acceptable.

Core Idea

For prefix sums, define \[ pref[i] = a_1 + a_2 + \cdots + a_i. \] Then the sum on \([l, r]\) becomes \[ pref[r] - pref[l - 1]. \]

For difference arrays, store changes instead of values: \[ diff[i] = a_i - a_{i-1}. \] To add \(x\) on \([l, r]\), do \[ diff[l] += x, \qquad diff[r + 1] -= x. \] One final prefix pass reconstructs the actual array.

Key Insight

Both techniques work by moving the work to boundaries.

  • Prefix sums answer an interval by looking only at its two ends.

  • Difference arrays mark only where an update starts and where it stops.

  • This boundary view is the reason they are so common in greedy checks, offline processing, and line-sweep style tasks.

Operations / Main Technique

Prefix-sum query.

Build once in \(O(n)\), answer each range sum in \(O(1)\).

Difference-array update.

Apply each range add in \(O(1)\), rebuild in \(O(n)\) at the end.

Worked example.

If I need to add \(+3\) on \([2, 5]\) and \(+4\) on \([4, 6]\), the difference array marks only four positions: \[ diff[2] += 3, \; diff[6] -= 3, \; diff[4] += 4, \; diff[7] -= 4. \] The prefix of \(\texttt{diff}\) then recreates the final values.

Correctness Intuition

For prefix sums, each interval sum is the full prefix to \(r\) minus the prefix before \(l\). Everything outside the interval cancels.

For difference arrays, a range update raises the running prefix by \(x\) starting at \(l\), and removes that extra contribution after \(r\). So every position inside the range sees \(x\), and every position outside does not.

Complexity Analysis

  • build prefix sums: \(O(n)\),

  • range sum query: \(O(1)\),

  • one difference-array range update: \(O(1)\),

  • reconstruct final array from differences: \(O(n)\),

  • memory: \(O(n)\).

Implementation

The code includes one small helper for static prefix sums and one helper for offline range additions with a difference array. Both are 0-indexed externally, which avoids repeated shifts in typical vector-based code.

Common Pitfalls

  • Forgetting the extra slot needed for \(\texttt{diff[r + 1]}\).

  • Mixing inclusive and half-open intervals.

  • Reaching for prefix sums when updates are online and frequent.

  • Using int for sums that should be long long.

  • Forgetting that prefix sums work for more than sums: counts, XOR, and weighted prefixes show up often too.

Variants / Extensions

  • Two-dimensional prefix sums for submatrix queries.

  • Two-dimensional difference arrays for rectangle updates.

  • Prefix sums over frequencies after coordinate compression.

  • Weighted prefix sums for fast range cost formulas.

Practice Problems

  • Many static range-sum queries on one array.

  • Offline interval additions followed by one final scan.

  • Counting active segments at every coordinate after compression.

  • Binary-search checkers that need fast range totals.

References

Implementation

Code

Contest-ready reference implementation for the idea explained above.

C++ competitive_programming/dsa/fundamentals/prefix-sums-and-difference-arrays/code.cpp

Kept as a standalone source file so the implementation can be copied without TeX markup around it.

Raw file 
struct PrefixSum {
    vector<long long> pref;

    explicit PrefixSum(const vector<long long>& a) : pref(a.size() + 1, 0) {
        for (int i = 0; i < (int)a.size(); ++i) {
            pref[i + 1] = pref[i] + a[i];
        }
    }

    long long query(int l, int r) const {
        return pref[r + 1] - pref[l];
    }
};

struct DifferenceArray {
    vector<long long> diff;

    explicit DifferenceArray(int n) : diff(n + 1, 0) {}

    void add_range(int l, int r, long long delta) {
        diff[l] += delta;
        if (r + 1 < (int)diff.size()) {
            diff[r + 1] -= delta;
        }
    }

    vector<long long> materialize() const {
        vector<long long> a(diff.size() - 1, 0);
        long long running = 0;
        for (int i = 0; i < (int)a.size(); ++i) {
            running += diff[i];
            a[i] = running;
        }
        return a;
    }
};
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Note TeXcompetitive_programming/dsa/fundamentals/prefix-sums-and-difference-arrays/note.texC++ codecompetitive_programming/dsa/fundamentals/prefix-sums-and-difference-arrays/code.cpp