guest@itl:~/home/data-structures$
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).

[Data Structures]|
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
#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)