Two-Dimensional Fenwick Tree
Extend the Fenwick tree idea to point updates and rectangle sums on a grid.
Two-Dimensional Fenwick Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
A 2D Fenwick tree is the direct generalization of the ordinary Fenwick tree from arrays to grids. It is the cleanest tool for:
point updates on a matrix,
prefix-sum queries on rectangles,
rectangle sums via inclusion-exclusion.
When to Use It
Use it when:
the data lives on a 2D grid,
updates touch one cell at a time,
queries ask for sums over axis-aligned rectangles.
If the grid is huge but only a few coordinates ever appear, combine it with coordinate compression first.
Core Idea
The one-dimensional Fenwick tree decomposes a prefix into power-of-two blocks. The 2D version does the same in both coordinates. Updating one cell climbs through all ancestors in the \(x\) dimension and, inside each of those, through all ancestors in the \(y\) dimension.
Key Insight
The logarithms multiply, not the dimensions of the whole grid. That is why the cost is \(O(\log n \log m)\) rather than linear in one direction.
Worked Problem
Problem.
Maintain a board where stars can be added or removed from cells, and answer the number of stars inside any rectangle \([x_1, x_2] \times [y_1, y_2]\).
Why 2D Fenwick fits.
Rectangle sums reduce to four prefix sums: \[ \texttt{sum}(x_2,y_2)-\texttt{sum}(x_1-1,y_2)-\texttt{sum}(x_2,y_1-1)+\texttt{sum}(x_1-1,y_1-1). \]
Correctness Intuition
Each cell contributes to exactly the 2D Fenwick blocks that cover it, just as in one dimension. Prefix queries collect exactly the blocks needed to tile the requested prefix rectangle without overlap.
Complexity Analysis
point update: \(O(\log n \log m)\),
prefix sum: \(O(\log n \log m)\),
rectangle sum: \(O(\log n \log m)\).
Implementation
The sample code supports point add and rectangle sum queries on a 1-indexed grid.
Common Pitfalls
Forgetting 1-indexing.
Accidentally allocating a full \(n \times m\) structure when compression was needed.
Using it when the problem really needs rectangle updates or range updates, which require extra machinery.
Variants / Extensions
Coordinate-compressed sparse 2D Fenwick tree.
Higher-dimensional Fenwick trees.
2D segment tree when the update/query model is more complicated.
Practice Problems
Point update and rectangle sum on a grid.
Dynamic counting of marked cells inside rectangles.
Compressed-coordinate rectangle query problems.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Fenwick2D {
int n;
int m;
vector<vector<long long>> bit;
Fenwick2D(int n, int m) : n(n), m(m), bit(n + 1, vector<long long>(m + 1, 0)) {}
void add(int x, int y, long long delta) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
bit[i][j] += delta;
}
}
}
long long prefix_sum(int x, int y) const {
long long result = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
result += bit[i][j];
}
}
return result;
}
long long rectangle_sum(int x1, int y1, int x2, int y2) const {
if (x1 > x2 || y1 > y2) return 0;
return prefix_sum(x2, y2)
- prefix_sum(x1 - 1, y2)
- prefix_sum(x2, y1 - 1)
+ prefix_sum(x1 - 1, y1 - 1);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.