1D/2D Prefix Sums & Difference Arrays for O(1) Range Updates

The Discrete Fundamental Theorem of Calculus

Given an array $A[0 \dots N-1]$ over an abelian group (such as $(\mathbb{Z}, +)$ or bitvectors under $\oplus$), define the 1-indexed prefix sum array $P[0 \dots N]$ with sentinel $P[0] = 0$ and recurrence $P[i] = P[i-1] + A[i-1]$ for $1 \le i \le N$. Any contiguous range sum over the inclusive 0-indexed interval $[L, R]$ reduces to a single subtraction:

$$\sum_{k=L}^{R} A[k] = P[R + 1] - P[L]$$

Notice why the $N+1$ length with sentinel $P[0] = 0$ is mandatory in clean systems code: it eliminates the branch if (L == 0) on every query. Conversely, define the Difference Array (discrete derivative) $D[0 \dots N]$ where $D[0] = A[0]$ and $D[i] = A[i] - A[i-1]$ for $1 \le i < N$. The prefix sum of $D$ reconstructs $A$:

$$A[i] = \sum_{k=0}^{i} D[k]$$

Because every element $A[i]$ for $i \in [L, R]$ includes $D[L]$ in its prefix sum, adding a scalar $\Delta$ to the entire subarray $A[L \dots R]$ only modifies two adjacent boundaries in $D$: $D[L] \mathrel{+}= \Delta$ and $D[R+1] \mathrel{-}= \Delta$.

Trade-off Matrix: Static vs. Batched vs. Dynamic Range Operations

Visualizing 2D Inclusion-Exclusion & Difference Array Boundaries

Prefix Sum + Hash Map Pattern for Subarray Sum Equals $K$

Production Implementation: Contiguous 2D Prefix Sum & 2D Difference Stencil

#include <cstdint>
#include <vector>

class FlatGrid2D {
  std::size_t rows_;
  std::size_t cols_;
  std::vector<std::int64_t> data_; // (rows_ + 1) * (cols_ + 2) for safe sentinel padding

  std::size_t idx(std::size_t r, std::size_t c) const noexcept {
    return r * (cols_ + 2) + c;
  }

public:
  FlatGrid2D(std::size_t rows, std::size_t cols)
      : rows_(rows), cols_(cols), data_((rows + 2) * (cols + 2), 0) {}

  // O(1) 2D Difference Array range update on 0-indexed inclusive [r1..r2] x [c1..c2]
  void range_add(std::size_t r1, std::size_t c1, std::size_t r2, std::size_t c2, std::int64_t delta) noexcept {
    // Shift to 1-indexed internal coordinates
    ++r1; ++c1; ++r2; ++c2;
    data_[idx(r1, c1)]         += delta;
    data_[idx(r1, c2 + 1)]     -= delta;
    data_[idx(r2 + 1, c1)]     -= delta;
    data_[idx(r2 + 1, c2 + 1)] += delta;
  }

  // O(R * C) in-place 2D prefix sum reconstruction (call once to materialize values,
  // or twice to turn a 2D difference array directly into a 2D prefix sum query table!)
  void materialize_prefix_sums() noexcept {
    for (std::size_t r = 1; r <= rows_; ++r) {
      for (std::size_t c = 1; c <= cols_; ++c) {
        data_[idx(r, c)] += data_[idx(r - 1, c)]
                          + data_[idx(r, c - 1)]
                          - data_[idx(r - 1, c - 1)];
      }
    }
  }

  // O(1) subrectangle sum query on 0-indexed inclusive [r1..r2] x [c1..c2]
  // Prerequisite: data_ holds 2D prefix sums
  std::int64_t query_rect(std::size_t r1, std::size_t c1, std::size_t r2, std::size_t c2) const noexcept {
    return data_[idx(r2 + 1, c2 + 1)]
         - data_[idx(r1,     c2 + 1)]
         - data_[idx(r2 + 1, c1)]
         + data_[idx(r1,     c1)];
  }
};