Prefix/Suffix array and Difference array

A prefix sum array stores the running total of an input sequence so that any range sum can be recovered by a single subtraction. A suffix sum is the same idea read from the right. A difference array is the dual construction: it stores consecutive differences so that range updates collapse into two point edits, and the original array is recovered by one prefix pass.

Together these tricks turn a class of range queries and range updates from linear per-operation into amortized constant. The canonical use case solved below is offline range-add followed by point queries: each update adds a value to a contiguous interval, and each query asks for the current value at a single index.

Codes

Python

from itertools import accumulate

def solve(xs):
    n, updates, queries = xs
    diff = [0] * (n + 1)
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v
    arr = list(accumulate(diff[:n]))
    return [arr[i] for i in queries]

C++

#include <vector>

std::vector<long long> solve(
    int n,
    const std::vector<std::array<long long, 3>>& updates,
    const std::vector<int>& queries)
{
    std::vector<long long> diff(n + 1, 0);
    for (const auto& u : updates) {
        diff[u[0]] += u[2];
        diff[u[1] + 1] -= u[2];
    }
    for (int i = 1; i < n; ++i) diff[i] += diff[i - 1];
    std::vector<long long> ans;
    ans.reserve(queries.size());
    for (int q : queries) ans.push_back(diff[q]);
    return ans;
}

Example

Loading Python runner...

Description

Run time analysis

$O(n + u + q)$ where $n$ is the array length, $u$ the number of updates, and $q$ the number of queries. Each update does two point edits on the difference array, the prefix-sum pass is linear in $n$, and each query is a direct array lookup.

Space analysis

$O(n)$ auxiliary for the difference array and the reconstructed values. Input updates and queries are not counted against auxiliary memory.

Proof of correctness

Let $A$ be the target array and $D$ its difference array, defined by $D[0] = A[0]$ and $D[i] = A[i] - A[i-1]$ for $i > 0$. Adding $v$ to the interval $[l, r]$ in $A$ changes exactly $D[l]$ by $+v$ and $D[r+1]$ by $-v$ — every other entry of $D$ is unaffected because consecutive differences inside the interval remain the same. After all updates are applied to $D$, the prefix sum $A[i] = \sum_{j \le i} D[j]$ reconstructs the final array by telescoping. A point query is then a direct lookup.

Extensions

Applications

Leetcode 1674 [Expected difficulty: 7]

• Leetcode 1674

This problem is a good example of using a difference array as a 1D line sweep over all possible pair sums. For each mirrored pair, we mark the ranges of target sums that cost two moves, one move, or zero moves, then sweep the difference array to find the minimum total cost.

Intuition

For a mirrored pair (a, b), the target complementary sum can range from 2 to 2 * limit. Without changing either value, only a + b costs zero moves. With one change, every sum from min(a, b) + 1 through max(a, b) + limit is reachable. All remaining sums cost two moves. The difference array lets us add those cost intervals for every pair and recover the total cost for each target sum with one prefix pass.

Solution

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        # use difference array
        da = [0] * (limit * 2 + 2)
        n = len(nums)
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            # 0 changes
            da[a + b] -= 1
            da[a + b + 1] += 1
            # 1 change
            da[min(a, b) + 1] -= 1
            da[max(a, b) + limit + 1] += 1
            # 2 changes
            da[2] += 2
            da[limit * 2 + 1] -= 2
        res, c = n, 0
        for i in range(2, limit * 2 + 1):
            c += da[i]
            res = min(res, c)
        return res

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 10.
• cp-algorithms — Fenwick tree
• cp-algorithms — Sparse table