guest@cp-base:~/home/range-queries$
templates/fenwick-tree-2d.cpp
compilable
$cat templates/fenwick-tree-2d

2D Fenwick Tree

2D Binary Indexed Tree for point updates and rectangle sum queries in O(log n * log m).

[Range Queries]|
Jul 9, 2026
|explanatory_notes.md|
#fenwick#bit#2d#matrix#range-sum
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1005;
ll bit[MAXN][MAXN];
int N, M;

void add(int x, int y, ll v) {
    for (int i = x; i <= N; i += i & -i)
        for (int j = y; j <= M; j += j & -j)
            bit[i][j] += v;
}

ll prefSum(int x, int y) {
    ll s = 0;
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            s += bit[i][j];
    return s;
}

ll query(int x1, int y1, int x2, int y2) {
    return prefSum(x2, y2) - prefSum(x1 - 1, y2)
         - prefSum(x2, y1 - 1) + prefSum(x1 - 1, y1 - 1);
}
26 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

2D Fenwick Tree

Extends 1D BIT to two dimensions. Supports point updates and rectangle sum queries.

How It Works

  • add(x, y, v) — update position (x,y)(x, y) by vv

  • prefSum(x, y) — prefix sum from (1,1)(1,1) to (x,y)(x,y)

  • query(x1, y1, x2, y2) — rectangle sum via 2D inclusion-exclusion:

    • query=S(x2,y2)−S(x1−1,y2)−S(x2,y1−1)+S(x1−1,y1−1)\text{query} = S(x_2, y_2) - S(x_1{-}1, y_2) - S(x_2, y_1{-}1) + S(x_1{-}1, y_1{-}1)

    When to Use

  • Matrix point updates with rectangle sum queries

  • Simpler alternative to 2D segment tree for additive operations

    • Complexity

  • Update / Query — O(log⁡n⋅log⁡m)O(\log n \cdot \log m)

  • Space — O(nm)O(nm)