2D and Higher-Dimensional Queries

Queries over a grid or a point set: rectangle sums, counts, dominance. The choice of structure depends almost entirely on whether the queries can go offline.

The decision table

Grid	Updates	Online?	Structure	Cost
Dense, $\le 2000^2$	none	✔	2D prefix sum	$O(1)$ query
Dense, $\le 2000^2$	point	✔	2D BIT	$O({\log }^2)$
Dense	rectangle add + rectangle sum	✔	four 2D BITs	$O({\log }^2)$
Sparse, large	none	✘	offline sweep + BIT	$O((n+q)\log n)$
Sparse, large	none	✔	persistent segment tree	$O(\log n)$
Sparse, large	point	✘	offline sweep, or CDQ	$O(n{\log }^{2}n)$
Sparse, large	point	✔	sparse 2D segment tree, or KD-tree	$O({\log }^2)$ / $O(\sqrt{n})$
3+ dimensions	any	✘	CDQ, nested	$O(n{\log }^{k-1}n)$
Non-rectangular regions	—	✔	KD-tree	$O(\sqrt{n})$

Go offline

The single most useful fact here: sort by one coordinate and sweep with a 1D BIT answers most 2D query problems in $O((n+q)\log n)$ time and $O(n)$ memory — better than any 2D structure on both axes. Reach for a genuinely 2D structure only when the queries must be online.

The offline sweep

Decompose each rectangle query into two (or four) prefix queries by inclusion-exclusion, then sort everything by $x$:

// count points inside each query rectangle
struct Ev { int x, y1, y2, id, sign; bool isPoint; };
sort(ev.begin(), ev.end(), [](const Ev& a, const Ev& b) {
    return a.x != b.x ? a.x < b.x : a.isPoint > b.isPoint;   // points before queries
});
BIT bit(maxY);
for (auto& e : ev) {
    if (e.isPoint) bit.add(e.y1, 1);
    else ans[e.id] += e.sign * bit.rangeSum(e.y1, e.y2);
}

The tie-break (points before queries at the same $x$) encodes whether the boundary is inclusive — get it wrong and off-by-one errors appear only on specific inputs.

2D prefix sums

$P[i][j]=P[i-1][j]+P[i][j-1]-P[i-1][j-1]+a[i][j],$
$\mathrm{sum}(r_1,c_1,r_2,c_2)=P[r_2][c_2]-P[r_1-1][c_2]-P[r_2][c_1-1]+P[r_1-1][c_1-1].$

The four-term formula is inclusion-exclusion; in $d$ dimensions it becomes $2^d$ terms. Beyond $d=3$ the constant makes it impractical.

The 2D difference array is the dual (rectangle update, read at the end) — see Difference Array.

Dominance counting

“For each point, how many others have both coordinates $\le$ it?”

Sort by $x$, sweep, and count with a BIT over $y$. $O(n\log n)$.

In three dimensions this becomes the 3D partial order problem, solved by CDQ in $O(n{\log }^{2}n)$ — sort by $x$, CDQ on $y$, BIT on $z$.

Rectangle union

Area, perimeter, or “how many rectangles cover each point”: a sweep line with a segment tree storing per-node counts and covered length. $O(n\log n)$. This tree needs no lazy propagation, because updates arrive in matching $+1/-1$ pairs.

KD-trees and their niche

A KD-tree answers rectangle queries in $O(\sqrt{n})$ and nearest-neighbour in $O(\log n)$ expected, with $O(n)$ memory, and supports insertions with periodic rebuilds.

Its real advantage is non-rectangular regions — circles, half-planes, arbitrary convex shapes — which BIT-based sweeps cannot express. For plain rectangles, the offline sweep wins.

Memory, the real constraint

Structure	Memory
2D prefix / 2D BIT	$O(nm)$
Merge sort tree / BIT of vectors	$O(n\log n)$
Persistent segment tree	$O(n\log n)$ ints
Offline sweep + BIT	$O(n)$
KD-tree	$O(n)$
2D segment tree (sparse)	$O(q{\log }^{2}n)$

A $2000\times 2000$ long long 2D BIT is 32 MB — near the limit. Above that, compress or go offline.

Higher dimensions

Each extra dimension costs a $\log$ (CDQ) or makes range queries $O(n^{1-1/d})$ (KD-tree). Beyond $d=3$ or 4, essentially every structure degenerates to a linear scan, and the right move is to find a reformulation that removes a dimension — often by sorting.

See also: 2D Fenwick · CDQ · Sweep Line