2D Fenwick and 2D Segment Tree

Range queries over a grid. The structures generalise, but the memory grows quickly, so choose carefully.

2D Fenwick tree

A BIT of BITs. Point update, prefix-rectangle query, both $O(\log n\log m)$.

struct BIT2D {
    int n, m;
    vector<vector<long long>> t;
    BIT2D(int n, int m) : n(n), m(m), t(n + 1, vector<long long>(m + 1, 0)) {}
 
    void update(int x, int y, long long v) {            // 1-indexed
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
                t[i][j] += v;
    }
    long long query(int x, int y) {                     // prefix sum of [1..x][1..y]
        long long s = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                s += t[i][j];
        return s;
    }
    long long rect(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

Memory $O(nm)$ — fine for $2000\times 2000$, impossible for $10^5\times 10^5$.

2D segment tree

A segment tree over rows, where each node holds a segment tree over columns.

	Build	Query	Update	Memory
2D BIT	$O(nm)$	$O(\log n\log m)$	$O(\log n\log m)$	$O(nm)$
2D segment tree	$O(nm)$	$O(\log n\log m)$	$O(\log n\log m)$	$O(nm)$
2D segment tree, sparse	—	$O({\log }^2)$	$O({\log }^2)$	$O(q{\log }^2)$

No lazy propagation in 2D

Range updates on a 2D segment tree with lazy propagation do not work in general — a lazy tag on a row node cannot be pushed into the column trees consistently. Options: a 2D BIT with the four-BIT range-update trick (sums only), a sqrt decomposition, or offline processing.

When the grid is sparse

With $n,m$ up to $10^9$ but only $q\le 2\cdot 10^5$ points, an $O(nm)$ structure is impossible. The options:

1. Compress both coordinates. If all queries are known offline, map the $O(q)$ distinct $x$ and $y$ values to $[0,q)$ and use a dense structure.

2. Merge sort tree / BIT of sorted vectors. Sort points by $x$; each BIT node stores the $y$ values of its range, sorted. Query with binary search inside each node. $O({\log }^{2}n)$ per query, $O(n\log n)$ memory, no updates.

3. Offline sweep + 1D BIT. Sort everything by $x$ and sweep, maintaining a 1D BIT over $y$. This is almost always the right answer: $O((n+q)\log n)$ time, $O(n)$ memory, and it handles updates.

4. Persistent segment tree. Version $i$ contains all points with $x\le i$; a rectangle query is the difference of two versions. Online, $O(\log n)$ per query, $O(n\log n)$ memory.

5. KD-tree. $O(\sqrt{n})$ per rectangle query, $O(n)$ memory, and it supports insertions and nearest-neighbour queries.

The offline sweep — usually the answer

// count points inside each query rectangle
// decompose each rectangle into 2 prefix queries via inclusion-exclusion on x
sort(events.begin(), events.end());          // by x
BIT bit(maxY);
for (auto& e : events) {
    if (e.isPoint) bit.update(e.y, 1);
    else ans[e.qid] += e.sign * bit.query(e.y1, e.y2);
}

$O((n+q)\log n)$ with $O(n)$ memory — strictly better than a 2D structure on both counts whenever the queries can be sorted.

The decision table

Grid size	Updates	Online?	Structure
$\le 2000^2$	point	yes	2D BIT
$\le 2000^2$	rectangle add, rectangle sum	yes	four 2D BITs
large, sparse	none	no	offline sweep + 1D BIT
large, sparse	none	yes	persistent segment tree
large, sparse	point	no	offline sweep (CDQ if 3 dimensions)
large, sparse	point	yes	sparse 2D segment tree, or KD-tree
3+ dimensions	any	no	CDQ divide and conquer

See also: Fenwick Tree · Merge Sort Tree · 2D Queries