templates/partial-sum-2d.cpp
compilable
$cat templates/partial-sum-2d
Partial Sum 2D (Difference Array)
2D difference array for O(1) range updates and O(n*m) final propagation.
#difference-array#2d#range-update#partial-sum
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T = ll>
void apply_rectangle(vector<vector<T>>& diff, int x1, int y1, int x2, int y2, T k = 1) {
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
diff[x1][y1] += k;
diff[x1][y2 + 1] -= k;
diff[x2 + 1][y1] -= k;
diff[x2 + 1][y2 + 1] += k;
}
template <typename T = ll>
void propagate_partial_2d(vector<vector<T>>& diff) {
int n = diff.size() - 2, m = diff[0].size() - 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) diff[i][j] += diff[i][j - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) diff[i][j] += diff[i - 1][j];
}
template <typename T = ll>
T get_partial_2d(vector<vector<T>>& diff, int x, int y) {
return diff[x][y];
}
void Solve() {
// write your code here
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) Solve();
return 0;
}42 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)
2D Difference Array — Range Updates + Point Queries
Quick Start
void Solve()
{
int n, m; cin >> n >> m;
vector> diff(n + 2, vector(m + 2, 0)); int q; cin >> q;
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
apply_rectangle(diff, x1, y1, x2, y2); // +1 to rectangle
}
propagate_partial_2d(diff); // propagate once
int x, y; cin >> x >> y;
cout << get_partial_2d(diff, x, y) << "\n"; // value at (x,y)
}
Functions
apply_rectangle(diff, x1, y1, x2, y2, k) — apply +k to rectangle [x1..x2]×[y1..y2]propagate_partial_2d(diff) — propagate all updates (call once after all updates)get_partial_2d(diff, x, y) — query value at (x, y)Notes
diff should be sized (n+2) x (m+2) to avoid boundary issues.propagate_partial_2d once after ALL apply_rectangle calls.k=1, change to apply different increments.