2D Fenwick Tree (2D Binary Indexed Tree)

A BIT of BITs: point update + rectangle sum on a grid in O(log n · log m). An update nests two upward lowbit walks (rows × columns), touching log n · log m cells. A rectangle sum is inclusion-exclusion of four top-left prefixes: +P(r2,c2) − P(r1-1,c2) − P(r2,c1-1) + P(r1-1,c1-1).

Update: O(log n · log m) Rect query: O(log n · log m) Memory: (n+1)(m+1) 1-indexed both axes
Fast Slow
Idle
Touched (update walk)
Accumulated (prefix walk)
Target cell
Query rectangle
n × m
8 × 8
log₂n · log₂m
9
Cells touched
0
Last op
-
Result
-
Point update
O(log n·log m)
Prefix(r,c)
O(log n·log m)
Rectangle sum
O(log n·log m)
Memory
O(n·m)
Static (no upd)
O(1) SAT

A — original grid (1-indexed)

T — 2D BIT cells

Trace

Pick a cell and press update to watch the nested upward walk touch O(log n · log m) BIT cells. Then press rectSum to watch the four inclusion-exclusion prefix rectangles add and subtract to isolate the target rectangle.

The left grid is the conceptual matrix A. The right grid is the BIT array T, where T[i][j] stores the sum of the responsibility rectangle rows [i−lowbit(i)+1, i] × cols [j−lowbit(j)+1, j]. Update walks UP (i+=lowbit, j+=lowbit); prefix walks DOWN (i−=lowbit, j−=lowbit). Only invertible aggregates (sum, XOR, count) work — for rectangle min/max use a 2D segment tree.