Skip to content

2D Segment Tree & 2D BIT

For a matrix of values, support rectangle sum (or min) with point updates—or range updates with a heavier structure.

2D prefix sums (static)

If the matrix does not change, 2D prefix arrays give \(O(1)\) rectangle sum.

2D Fenwick (BIT)

One BIT nested in another: update \((x,y)\) and query prefix rectangle \([1..x][1..y]\) in \(O(\log n \log m)\). Good for point update + rectangle query.

// Fenwick 2D: implement update(x,y,delta) and sum(x,y) prefix; then
// rect(a,b,c,d) = sum(c,d) - sum(a-1,d) - sum(c,b-1) + sum(a-1,b-1)

Implementation uses vector of BITs or a single flattened index trick depending on constraints.

2D segment tree

Nested segments: each row (or column) holds a segment tree; updates/queries split in both dimensions—\(O(\log n \log m)\) per operation typically.