xiii. Offline and 2D Range Queries

Most “2D” problems (points in rectangles, range queries with a value condition, distinct values in a range) become 1D after sorting by one coordinate and sweeping with a Fenwick tree over the other. That’s $O((n+q)\log n)$ time and $O(n)$ memory, better than any 2D structure on both counts. Use a genuinely 2D structure only when the queries are forced online.

Choosing a structure

Grid / points	Updates	Online	Structure	Cost per op
dense, $\le 2000^2$	none	yes	2D prefix sums	$O(1)$
dense	point	yes	2D Fenwick (Fenwick)	$O({\log }^2)$
dense	rectangle add + rectangle sum	yes	four 2D Fenwicks	$O({\log }^2)$
sparse, large coordinates	none	no	sweep + Fenwick	$O(\log n)$
sparse	none	yes	persistent segment tree / wavelet matrix	$O(\log n)$
sparse	point	no	CDQ (CDQ) or offline Fenwick of Fenwicks	$O({\log }^{2}n)$
sparse	point	yes	Fenwick of sorted vectors with inner Fenwicks, or KD-tree	$O({\log }^{2}n)$ / $O(\sqrt{n})$
non-rectangular region (half-plane, circle)	any	yes	KD-tree (KD-Tree)	$O(\sqrt{n})$
$d\ge 3$ dimensions	any	no	nested CDQ	$O(n{\log }^{d-1}n)$

Points in rectangles (offline sweep)

Write the rectangle $[x_1,x_2)\times [y_1,y_2)$ as “prefix $x<x_2$” minus “prefix $x<x_1$”. Sort points and these events by $x$; insert points into a Fenwick over compressed $y$ when the sweep passes them.

vector<ll> rectSum(vector<array<ll, 3>> pts, const vector<array<ll, 4>>& qs) {   // pts {x, y, w}, qs {x1, x2, y1, y2}
    vector<ll> ys; for (auto& p : pts) ys.push_back(p[1]);
    sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
    auto yi = [&](ll y) { return int(lower_bound(all(ys), y) - ys.begin()); };
    sort(all(pts));
    vector<tuple<ll, int, int>> ev;                    // (x, query, sign): uses points with px < x
    for (int i = 0; i < sz(qs); i++) ev.emplace_back(qs[i][0], i, -1), ev.emplace_back(qs[i][1], i, 1);
    sort(all(ev));
    Fenwick<ll> fw(sz(ys)); vector<ll> res(sz(qs)); int p = 0;
    for (auto [x, i, s] : ev) {
        for (; p < sz(pts) && pts[p][0] < x; p++) fw.add(yi(pts[p][1]), pts[p][2]);
        res[i] += s * fw.sum(yi(qs[i][2]), yi(qs[i][3]));
    }
    return res;
}

With half-open rectangles, “points with $p_x<x$” is the whole tie-break rule. With closed rectangles, decide explicitly whether points at the same $x$ are processed before the query; most off-by-ones live there.

Dominance counting (“for each point, how many points are $\le$ it in both coordinates”) is the same sweep. With a third coordinate it’s the 3D partial order problem, solved by CDQ in $O(n{\log }^{2}n)$.

Static rectangle add

Read at points: a rectangle add is four signed corners of a 2D difference array; the value at $(x,y)$ is the sum of corners with $x_0\le x$, $y_0\le y$, which is a dominance sum, so the same sweep applies.

Read over rectangles: keep four Fenwicks over $y$ of corner weights $w$, $w{x}_0$, $w{y}_0$, $w{x}_0{y}_0$ (with sign), and evaluate

$S(X,Y)=XY\sum w-Y\sum w{x}_0-X\sum w{y}_0+\sum w{x}_0{y}_0$

over the corners with $x_0<X$, $y_0<Y$, where $S(X,Y)$ is the sum of all cells $[0,X)\times [0,Y)$. A query rectangle is four signed prefix values. Values reach $w\cdot 10^{18}$, so use __int128 or a modular type. Library Checker exercises this exact family: “Static Rectangle Add Rectangle Sum”, “Rectangle Sum”, “Rectangle Add Point Get”.

Proof: the four-Fenwick formula

The cell value is $v(x,y)={\sum }_{\text{corners }(x_0,y_0,s)}sw[x_0\le x][y_0\le y]$ (2D difference array). Summing over the cells with $x<X$ and $y<Y$, a corner with $x_0<X$ and $y_0<Y$ contributes $sw$ for each of the $(X-x_0)(Y-y_0)$ cells it dominates, and other corners contribute nothing. Expanding $(X-x_0)(Y-y_0)=XY-Y{x}_0-X{y}_0+x_0{y}_0$ separates the query coordinates from the corner coordinates, so each of the four sums is a dominance sum over corners, maintained by one Fenwick each during the sweep.

Distinct values in a range

Let ${\text{prev}}_i$ be the previous index with the same value ($-1$ if none). The number of distinct values in $[l,r)$ equals the number of $i\in [l,r)$ with ${\text{prev}}_i<l$, a 2D dominance count.

• Offline: sweep $r$; when $r$ enters, add $+1$ at $r$ and $-1$ at ${\text{prev}}_r$; the answer is the Fenwick sum over $[l,r)$.
• Online: a persistent segment tree, version $r$ = the array above after processing $r$ (PST).
• With point updates: a point update changes $\text{prev}$ of $O(1)$ positions (found with a set per value), so it’s dominance counting with insertions and deletions: CDQ over time, $O((n+q){\log }^{2}n)$.

vector<int> distinct(const vector<int>& a, const vector<pair<int, int>>& qs) {   // [l, r)
    int n = sz(a); vector<vector<int>> at(n + 1); vector<int> res(sz(qs));
    for (int i = 0; i < sz(qs); i++) at[qs[i].second].push_back(i);
    map<int, int> last; Fenwick<int> fw(n);
    for (int r = 0; r <= n; r++) {
        for (int i : at[r]) res[i] = fw.sum(qs[i].first, r);
        if (r == n) break;
        if (auto it = last.find(a[r]); it != last.end()) fw.add(it->second, -1);
        fw.add(r, 1); last[a[r]] = r;
    }
    return res;
}

Proof: the sweep counts exactly the distinct values

After processing positions $\mathrm{0..}r-1$, the Fenwick holds a 1 exactly at the last occurrence (before $r$) of each value. A value occurs in $[l,r)$ iff its last occurrence before $r$ is $\ge l$. So the sum over $[l,r)$ counts each value present in the range exactly once.

The same “keep only the last occurrence” sweep gives the sum of distinct values, “is there a duplicate”, the minimum gap between equal values, and range mex (Offline Techniques).

Area of a union of rectangles

Sweep $x$; a segment tree over the elementary $y$-intervals keeps cnt[v] (how many active rectangles cover node $v$‘s whole range as a canonical node) and len[v] (covered length inside $v$‘s range). No lazy propagation is needed.

struct Cover {
    int n; vector<ll> ys, len; vector<int> cnt;                // elementary intervals [ys[i], ys[i+1])
    Cover(vector<ll> y) : ys(y), n(sz(y) - 1), len(4 * sz(y)), cnt(4 * sz(y)) {}
    void upd(int v, int l, int r, int ql, int qr, int d) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) cnt[v] += d;
        else { int m = (l + r) / 2; upd(2 * v, l, m, ql, qr, d); upd(2 * v + 1, m, r, ql, qr, d); }
        len[v] = cnt[v] ? ys[r] - ys[l] : r - l == 1 ? 0 : len[2 * v] + len[2 * v + 1];
    }
};
// events (x, y1, y2, +1/-1) sorted by x; area += len[1] * (x_next - x) between consecutive events

Perimeter: add $|{\text{len}}_{\text{after}}-{\text{len}}_{\text{before}}|$ at every event for the vertical edges, and do the same sweep in $y$ for horizontal ones (or track the number of covered segments per node). “Area covered by at least $k$ rectangles”: store len for coverage $\ge \mathrm{1..}k$ per node.

Proof: len[1] is the covered length

Invariant: $\text{len}[v]$ equals the length of the part of $v$‘s range covered by the intervals currently assigned (as canonical nodes) to $v$ or its descendants. If $\text{cnt}[v]>0$, an interval covers all of $v$‘s range, so the whole range counts. Otherwise the covered part is the union of the children’s covered parts. Each update recomputes len on exactly the nodes whose subtree changed (the canonical nodes and their ancestors). Every removal hits the same canonical nodes as the matching insertion, so cnt never goes negative and nothing has to be pushed down: intervals assigned to an ancestor are accounted for by the ancestor’s cnt. At the root, the invariant is the covered length of the union.

Online 2D with point updates

• Fenwick of sorted vectors: for each Fenwick node over $x$, collect (offline) all $y$ values that will ever be inserted into it, sort, and give it an inner Fenwick. Updates and queries are $O({\log }^{2}n)$ with $O(n\log n)$ memory. This needs the set of points in advance but answers queries online.
• Fenwick of ordered_set when even that is not known, with a larger constant.
• Sparse 2D segment tree (segment tree over $x$ whose nodes are dynamic segment trees over $y$): $O({\log }^{2}n)$ time and $O(q{\log }^{2}n)$ memory, often too much.
• KD-tree with periodic rebuilds: $O(\sqrt{n})$ per query, $O(n)$ memory.

Rules of thumb

• If a query has two conditions ($l\le i<r$ and $a_i\le x$), sweep one and index the other.
• Three conditions: sweep one, CDQ on the second, Fenwick on the third.
• 2D difference arrays: inclusion-exclusion with $2^d$ corners; beyond $d=3$ find a reformulation that removes a dimension.
• Memory: a $2000\times 2000$ long long 2D Fenwick is 32 MB.