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

2D Segment Tree

Nested segment tree for 2D point update and rectangle queries in O(log n * log m).

[Range Queries]|
Jul 9, 2026
|explanatory_notes.md|
#segment-tree#2d#matrix#range-query
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1005;
ll tree[4 * MAXN][4 * MAXN];
ll IDENTITY = 0;
int N, M;

ll combine(ll a, ll b) { return a + b; }

void buildY(int vx, int lx, int rx, int vy, int ly, int ry, ll grid[][MAXN]) {
    if (ly == ry) {
        if (lx == rx) tree[vx][vy] = grid[lx][ly];
        else tree[vx][vy] = combine(tree[2*vx][vy], tree[2*vx+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        buildY(vx, lx, rx, 2*vy, ly, my, grid);
        buildY(vx, lx, rx, 2*vy+1, my+1, ry, grid);
        tree[vx][vy] = combine(tree[vx][2*vy], tree[vx][2*vy+1]);
    }
}

void buildX(int vx, int lx, int rx, ll grid[][MAXN]) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        buildX(2*vx, lx, mx, grid);
        buildX(2*vx+1, mx+1, rx, grid);
    }
    buildY(vx, lx, rx, 1, 1, M, grid);
}

void build(ll grid[][MAXN]) { buildX(1, 1, N, grid); }

void updateY(int vx, int lx, int rx, int vy, int ly, int ry, int y, ll val) {
    if (ly == ry) {
        if (lx == rx) tree[vx][vy] = val;
        else tree[vx][vy] = combine(tree[2*vx][vy], tree[2*vx+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        if (y <= my) updateY(vx, lx, rx, 2*vy, ly, my, y, val);
        else updateY(vx, lx, rx, 2*vy+1, my+1, ry, y, val);
        tree[vx][vy] = combine(tree[vx][2*vy], tree[vx][2*vy+1]);
    }
}

void updateX(int vx, int lx, int rx, int x, int y, ll val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx) updateX(2*vx, lx, mx, x, y, val);
        else updateX(2*vx+1, mx+1, rx, x, y, val);
    }
    updateY(vx, lx, rx, 1, 1, M, y, val);
}

void update(int x, int y, ll val) { updateX(1, 1, N, x, y, val); }

ll queryY(int vx, int vy, int ly, int ry, int y1, int y2) {
    if (ly > y2 || ry < y1) return IDENTITY;
    if (ly >= y1 && ry <= y2) return tree[vx][vy];
    int my = (ly + ry) / 2;
    return combine(queryY(vx, 2*vy, ly, my, y1, y2),
                   queryY(vx, 2*vy+1, my+1, ry, y1, y2));
}

ll queryX(int vx, int lx, int rx, int x1, int x2, int y1, int y2) {
    if (lx > x2 || rx < x1) return IDENTITY;
    if (lx >= x1 && rx <= x2) return queryY(vx, 1, 1, M, y1, y2);
    int mx = (lx + rx) / 2;
    return combine(queryX(2*vx, lx, mx, x1, x2, y1, y2),
                   queryX(2*vx+1, mx+1, rx, x1, x2, y1, y2));
}

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

2D Segment Tree

Nested segment tree: outer tree indexes rows, each outer node contains an inner segment tree over columns.

Operations

  • build(grid) — construct from 2D array

  • update(x, y, val) — point update at (x,y)(x, y)

  • query(x1, x2, y1, y2) — rectangle aggregate query

    • How It Works

  • Row range [r1,r2][r_1, r_2] decomposes into O(log⁡n)O(\log n) outer segments

  • For each, the inner tree is queried over [c1,c2][c_1, c_2] in O(log⁡m)O(\log m)

  • Point update propagates through outer tree, rebuilding inner trees along the path

    • Customization

  • Change combine() and IDENTITY for different operations (sum, min, max, etc.)

    • When to Use

  • 2D range queries with point updates

  • Matrix problems requiring online updates

    • Complexity

  • Build — O(nm)O(nm)

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

  • Space — O(16nm)O(16nm)