Partial Sum 2D (Difference Array)

2D difference array for O(1) range updates and O(n*m) final propagation.

[Range Queries]|

Jul 9, 2026

|explanatory_notes.md|

#difference-array#2d#range-update#partial-sum

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1005;
ll diff[MAXN][MAXN];
int N, M;

void update(int x1, int y1, int x2, int y2, ll k = 1) {
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    diff[x2][y2]         += k;
    diff[x2][y1 - 1]     -= k;
    diff[x1 - 1][y2]     -= k;
    diff[x1 - 1][y1 - 1] += k;
}

void propagate() {
    for (int i = N; i >= 0; i--)
        for (int j = M; j >= 0; j--)
            diff[i][j] += diff[i][j + 1];
    for (int i = N; i >= 0; i--)
        for (int j = M; j >= 0; j--)
            diff[i][j] += diff[i + 1][j];
}

ll get(int x, int y) {
    return diff[x][y];
}

29 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

2D Difference Array

Batch rectangle updates in $O(1)$ each, then propagate once to get the final grid.

How It Works

To add $k$ to every cell in rectangle $(x_1, y_1)$ to $(x_2, y_2)$ , mark four corners:

d[x_2][y_2] \mathrel{+}= k

d[x_2][y_1 - 1] \mathrel{-}= k

d[x_1 - 1][y_2] \mathrel{-}= k

d[x_1 - 1][y_1 - 1] \mathrel{+}= k

After all updates, propagate with two passes:

Row-wise (right to left):

d[i][j] \mathrel{+}= d[i][j+1]

Column-wise (bottom to top):

d[i][j] \mathrel{+}= d[i+1][j]

When to Use

Batch rectangle additions followed by reading the final grid

Counting how many rectangles cover each cell

Overlapping range problems (sweep line alternative)

Complexity

Update —

O(1)

Propagate —

O(n \cdot m)

Query (after propagate) —

O(1)

Space —

O(n \cdot m)