Optional: sparse values and rectangle updates
Compress an enormous value domain or extend difference markers to a grid.
Compression preserves order, not distance
Coordinate compression sorts the distinct keys and gives each its zero-based position as a compact ID. For [−10⁹, 7, 7, 10⁹, 50], distinct keys are [−10⁹, 7, 50, 10⁹]. Count occurrences by those IDs, then build a frequency prefix.
To query values in [L, R], use lower_bound(L) and upper_bound(R) on the sorted distinct-key vector. Their positions form a half-open ID interval; subtract its prefix boundaries. Query endpoints do not need to occur as keys. Compression preserves equality and sorted order, but adjacent IDs do not imply original values are one unit apart.
Choose the simplest static representation
Compression with frequencies takes O(n log(n + 1)) preprocessing, O(log(d + 1)) per query, and O(n + d) storage. For occurrence counts alone, sorting all observations while keeping duplicates and subtracting two bound positions is even simpler.
Use compression when other information is attached to distinct keys or a compact indexed domain is needed. A geometric length or area problem must retain original coordinate distances; counting compressed IDs would lose the gaps.
Four corners for a rectangular addition
For an initially zero grid, add delta inside inclusive corners (r1,c1) and (r2,c2). Record +delta at (r1,c1), −delta at (r2+1,c1), −delta at (r1,c2+1), and +delta at (r2+1,c2+1). Two-dimensional prefix reconstruction spreads and cancels those contributions.
Allocate two extra rows and columns for the stopping boundaries, and print only real cells. The batch method costs O(RC + u) time and O(RC) storage. After in-place reconstruction, entries contain values rather than raw markers; do not append new markers to that changed representation. It handles addition, not assignment.
// Complete C++23 program. Input: rows cols u, then r1 c1 r2 c2 delta.
// Start with a zero grid. Inclusive valid rectangles; all updates first.
#include <iostream>
#include <vector>
int main() {
int rows, cols, u;
std::cin >> rows >> cols >> u;
std::vector<std::vector<long long>> diff(
rows + 2, std::vector<long long>(cols + 2, 0));
for (int j = 0; j < u; ++j) {
int r1, c1, r2, c2;
long long delta;
std::cin >> r1 >> c1 >> r2 >> c2 >> delta;
diff[r1][c1] += delta;
diff[r2 + 1][c1] -= delta;
diff[r1][c2 + 1] -= delta;
diff[r2 + 1][c2 + 1] += delta;
}
for (int r = 1; r <= rows; ++r) {
for (int c = 1; c <= cols; ++c) {
diff[r][c] += diff[r - 1][c] + diff[r][c - 1]
- diff[r - 1][c - 1];
if (c > 1) std::cout << ' ';
std::cout << diff[r][c];
}
std::cout << '\n';
}
}Compressed keys are [−10⁹, 7, 50, 10⁹]. How many observations from [−10⁹,7,7,10⁹,50] lie in [8,49]?
Turn the idea into code
In a 2×3 zero grid, add 4 to rows 1..2, columns 1..2, then add −1 to row 2, columns 2..3. Write the final grid.
Give me a hint
The overlap at row 2, column 2 receives both additions.
Show the explained solution
The first row is [4, 4, 0] and the second is [4, 3, −1]. The four-corner method combines each update’s contribution and reconstructs exactly these cell values.
Your notes
Mark complete when you can explain it yourself.