2D Segment Tree - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const int N = 1024;
int tree[4*N][4*N];

int n,m;

int mrg(int a, int b) {
    return a+b;
}

int gety(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry)
        return 0;
    if (ly == tly && try_ == ry)
        return tree[vx][vy];
    int tmy = (tly + try_) / 2;
    int n1 = gety(vx, vy*2+1, tly, tmy, ly, min(ry, tmy));
    int n2 = gety(vx, vy*2+2, tmy+1, try_, max(ly, tmy+1), ry);
    return mrg(n1,n2);
}

int get(int lx, int rx, int ly, int ry, int vx = 0, int tlx = 0, int trx = n-1) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return gety(vx, 0, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    int n1 = get(lx, min(rx, tmx), ly, ry, vx*2+1, tlx, tmx);
    int n2 = get(max(lx, tmx+1), rx, ly, ry,vx*2+2, tmx+1, trx);
    return mrg(n1,n2);
}

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



void update(int x, int y, int val, int vx = 0, int lx = 0, int rx = n-1) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update(x, y, val, vx*2+1, lx, mx);
        else
            update(x, y, val, vx*2+2, mx+1, rx);
    }
    update_y(vx, lx, rx, 0, 0, m-1, x, y, val);
}

void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ly == ry) {
        if (lx == rx)
            tree[vx][vy] = a[lx][ly];
        else
            tree[vx][vy] = mrg(tree[vx*2+1][vy], tree[vx*2+2][vy]);
    } else {
        int my = (ly + ry) / 2;
        build_y(vx, lx, rx, vy*2+1, ly, my);
        build_y(vx, lx, rx, vy*2+2, my+1, ry);
        tree[vx][vy] = mrg(tree[vx][vy*2+1] , tree[vx][vy*2+2]);
    }
}
 
void build_x(int vx = 0, int lx = 0, int rx = n-1) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        build_x(vx*2+1, lx, mx);
        build_x(vx*2+2, mx+1, rx);
    }
    build_y(vx, lx, rx, 0, 0, m-1);
}

int main() {
    SaveTime
    // build by build_x
    // zero indexed
}