How the Prefix Sum Technique Works for Range Queries: A Complete Guide

The prefix sum technique preprocesses an array in O(N) time to create a cumulative sum array, allowing any range sum query to be answered in O(1) time by subtracting two prefix values.

The prefix sum technique is a fundamental algorithmic pattern for solving range query problems efficiently. In the azl397985856/leetcode repository, this technique appears in solutions for problems like corporate flight bookings and sliding window scenarios. By transforming a static array into a cumulative representation, the prefix sum technique eliminates the need to iterate through subarrays repeatedly.

What Is the Prefix Sum Technique?

The prefix sum technique (also called cumulative sum) converts an input array into a helper array where each element at index i stores the sum of all elements from the start of the array up to and including position i.

For an input array A, the prefix array P is defined as:

P[i] = A[0] + A[1] + ... + A[i]

This preprocessing step requires a single linear pass through the original array, resulting in O(N) time complexity and O(N) additional space (or O(1) if modifying the array in-place).

How Prefix Sums Answer Range Queries in O(1) Time

Once the prefix array is constructed, calculating the sum of any contiguous subarray becomes a constant-time operation. The mathematical relationship depends on your indexing scheme.

For 1-based indexing:

sum[l … r] = prefix[r] - prefix[l-1]

For 0-based indexing:

sum[l … r] = prefix[r] - (prefix[l-1] if l > 0 else 0)

This works because prefix[r] contains the sum of elements from index 0 through r, while prefix[l-1] contains the sum from index 0 through l-1. Subtracting these values isolates exactly the elements from l to r.

Implementation Examples from the LeetCode Repository

The azl397985856/leetcode repository demonstrates the prefix sum technique in several contexts, from basic range queries to advanced difference array applications.

Basic Prefix Sum Construction

The core implementation builds the prefix array in a single pass. Here is the Python pattern used throughout the repository:

def build_prefix(nums):
    """Return prefix array where prefix[i] = sum(nums[:i+1])"""
    prefix = [0] * len(nums)
    cur = 0
    for i, v in enumerate(nums):
        cur += v
        prefix[i] = cur
    return prefix

def range_sum(prefix, l, r):
    """0-based inclusive range [l, r]"""
    return prefix[r] - (prefix[l-1] if l > 0 else 0)

# Example usage

arr = [1, 2, 3, 4, 5]
pref = build_prefix(arr)
print(range_sum(pref, 1, 3))   # Output: 9 (2+3+4)

Difference Array for Range Updates

The repository extends the prefix sum concept to handle range addition operations efficiently. In the flight booking problem (LeetCode 1109), the solution uses a difference array (inverse of prefix sum) to process multiple range updates in O(N) time.

The pattern works by marking the start of a range with +k and the position after the end with -k. A final prefix sum pass converts these markers into the actual values:

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 1)                 # Extra slot for sentinel

    for i, j, k in bookings:             # [i, j] inclusive, 1-based

        diff[i-1] += k
        if j < n:
            diff[j] -= k
    # Convert difference array to result using prefix sum

    for i in range(1, n):
        diff[i] += diff[i-1]
    return diff[:n]

This approach demonstrates how prefix sums serve as both a query mechanism and a tool for efficient range modifications.

Key Files in the Repository

The prefix sum technique appears throughout the azl397985856/leetcode repository. These files contain the core implementations and explanations:

• thinkings/prefix.md — Core tutorial explaining the prefix sum concept and its application to range queries, including the toy example [1,2,3,4,5,6] → pre=[1,3,6,10,15,21].
• thinkings/prefix.en.md — English translation of the prefix sum tutorial for international readers.
• thinkings/slide-window.md — Demonstrates how prefix sums combine with sliding window techniques to solve subarray problems efficiently.
• problems/1109.corpFlightBookings.md — Solution for Corporate Flight Bookings using the difference array variant of prefix sums to handle range additions.

Summary

• The prefix sum technique preprocesses an array in O(N) time to create a cumulative sum array.
• Range sum queries become O(1) operations using the formula prefix[r] - prefix[l-1].
• The technique extends to difference arrays for efficient range updates, as demonstrated in the flight booking solution.
• Key implementations reside in thinkings/prefix.md and problems/1109.corpFlightBookings.md within the azl397985856/leetcode repository.

Frequently Asked Questions

What is the time complexity of building a prefix sum array?

Building the prefix sum array requires a single pass through the original array, resulting in O(N) time complexity where N is the length of the array. This preprocessing step happens once before any queries are processed.

Can prefix sums handle dynamic arrays where elements change frequently?

Standard prefix sums are designed for static arrays where the data does not change after preprocessing. If elements update frequently, the prefix array would need to be rebuilt after each change, costing O(N) per update. For dynamic scenarios, consider using a Binary Indexed Tree (Fenwick Tree) or Segment Tree instead.

How does the difference array relate to prefix sums?

The difference array is the inverse operation of the prefix sum. While prefix sums convert point values into cumulative totals, difference arrays store the changes between consecutive elements. Applying a prefix sum to a difference array reconstructs the original values. This relationship enables efficient range updates—mark the start with +k and the position after the end with -k, then compute prefix sums to get final values, as shown in the flight booking solution.

What is the space complexity of the prefix sum technique?

The prefix sum technique requires O(N) additional space to store the cumulative sum array, where N is the number of elements in the original array. However, if you can modify the input array in-place, the space complexity can be reduced to O(1) by overwriting the original values with their cumulative sums.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}