Prefix Sum Fundamentals

The prefix sum technique converts range sum queries from O(n) per query to O(1) by preprocessing the array once.

Given an array of n integers and m queries asking for the sum of elements between indices l and r (inclusive), the naive approach processes each query by iterating through the range. With prefix sums, we build a cumulative sum array where each position stores the sum of all elements up to that point. The answer to any query becomes a simple subtraction: prefix[r] - prefix[l-1].

Building the Prefix Sum Array:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> data(n + 1);
    vector<long long> prefix(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> data[i];
    }
    
    prefix[1] = data[1];
    for (int i = 2; i <= n; i++) {
        prefix[i] = data[i] + prefix[i - 1];
    }
    
    for (int i = 0; i < q; i++) {
        int left, right;
        cin >> left >> right;
        long long result = prefix[right] - (left > 1 ? prefix[left - 1] : 0);
        cout << result << '\n';
    }
    
    return 0;
}

Time Complexity: O(n + m) for preprocessing and answering queries.

Difference Arrays: The Inverse Operation

Difference arrays represent the inverse of prefix sums. Instead of answering queries, they efficiently handle range updates where we need to add a constant value to all element in an interval [l, r].

The core insight: instead of modifying each element in the range (O(n) per operation), we manipulate a difference array of length n+1. To add value c to range [l, r], we perform two operations: diff[l] += c and diff[r+1] -= c. After processing all updates, computing the prefix sum of the difference array yields the final modified array.

Implementing Range Updates with Difference Arrays:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, operations;
    cin >> n >> operations;
    
    vector<int> original(n);
    vector<int> diff(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> original[i];
    }
    
    // Build difference array from original
    diff[0] = original[0];
    for (int i = 1; i < n; i++) {
        diff[i] = original[i] - original[i - 1];
    }
    
    // Apply range updates
    for (int i = 0; i < operations; i++) {
        int left, right, value;
        cin >> left >> right >> value;
        diff[left - 1] += value;
        if (right < n) {
            diff[right] -= value;
        }
    }
    
    // Reconstruct final array via prefix sum
    int current = 0;
    for (int i = 0; i < n; i++) {
        current += diff[i];
        cout << current << (i < n - 1 ? " " : "\n");
    }
    
    return 0;
}

Key Properties:

• Range update: diff[l] += c, diff[r+1] -= c
• Point query: prefix sum of diff up to index i
• Time complexity: O(n + m) for m operations on n elements

When to Use Each Technique

Prefix sums excel when queries vastly outnumber updates—each query becomes O(1) after O(n) preprocessing. Difference arrays shine when updates dominate queries, converting O(n) range updates into O(1) operations. Together, these complementary techniques form the foundation for efficient range query and update operations in competitive programming and system design.