Segment tree

2D BIT.cpp

int N, M;
int bit[MAXN][MAXN];
int sum(int x, int y) {
    int ret = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
            ret += bit[i][j];
    return ret;
}
void add(int x, int y, int delta) {
    for (int i = x; i < N; i = i | (i + 1))
        for (int j = y; j < M; j = j | (j + 1))
            bit[i][j] += delta;
}

2D Seg.cpp

struct seg {
    int seg[2 * MAXN][2 * MAXN];
    void modify(int qr, int qc, int val) {
        qr += N, qc += M;
        seg[qr][qc] = val;
        for (int r = qr; r > 0; r >>= 1) {
            for (int c = qc; c > 0; c >>= 1)
                seg[r][c >> 1] = seg[r][c] + seg[r][c ^ 1];
            seg[r >> 1][qc] = seg[r][qc] + seg[r ^ 1][qc];
        }
    }
    int query2(int l, int r, int row) {
        int res = 0;
        for (l += M, r += M; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                res += seg[row][l++];
            if (r & 1)
                res += seg[row][--r];
        }
        return res;
    }
    int query(int u, int d, int l, int r) {
        int res = 0;
        for (u += N, d += N; u < d; u >>= 1, d >>= 1) {
            if (u & 1)
                res += query2(l, r, u++);
            if (d & 1)
                res += query2(l, r, --d);
        }
        return res;
    }
};

abstract.cpp

template <typename T> struct Seg {
    const int N;
    vector<T> seg;
    T unit;
    const function<T(T, T)> combine;
    Seg(int n, T arr[], T u, function<T(T, T)> cF) : N(n), unit(u), combine(cF), seg(N * 2) {
        for (int i = 0; i < N; i++)
            seg[i + N] = arr[i];
        build();
    }
    void build() {
        for (int i = N - 1; i > 0; --i)
            seg[i] = combine(seg[i << 1], seg[i << 1 | 1]);
    }

    void modify(int p, T value) {
        for (seg[p += N] = value; p > 0; p >>= 1)
            seg[p>>1] = combine(seg[p], seg[p ^ 1]);
    }

    T query(int l, int r) {
        T resl = unit;
        T resr = unit;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1)
                resl = combine(resl, seg[l++]);
            if (r & 1)
                resr = combine(seg[--r], resr);
        }
        return combine(resl, resr);
    }
};

dynamic.cpp

gp_hash_table<int, int, chash> seg;

int get(int x) { return (seg.find(x) == seg.end()) ? 0 : seg[x]; }
void modify(int p, int val) {
    for (seg[p += N] = val; p > 0; p >>= 1) {
        seg[p >> 1] = get(p) + get(p ^ 1);
    }
}

int query(int l, int r) {
    int res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += get(l++);
        if (r & 1)
            res += get(--r);
    }
    return res;
}

lazy propagation.cpp

struct Tree {
    Tree *pl, *pr;
    int nl = 0, nr = 0, val = 0, lazy = 0;

    void updateVal() { val = pl->val + pr->val; }
    void propagate() { pl->apply(lazy), pr->apply(lazy), lazy = 0; }
    void apply(int x) { lazy += x, val += (nr - nl) * x; }

    Tree(int l, int r, int A[]) {
        nl = l, nr = r;
        if (nl + 1 == nr) {
            val = A[nl];
            return;
        }
        pl = new Tree(nl, nl + nr >> 1, A);
        pr = new Tree(nl + nr >> 1, nr, A);
        updateVal();
    }
    void modify(int l, int r, int x) {
        if (l <= nl && nr <= r) {
            apply(x);
            return;
        }
        if (l >= nr || nl >= r)
            return;
        propagate();
        pl->modify(l, r, x);
        pr->modify(l, r, x);
        updateVal();
    }
    int query(int l, int r) {
        if (l <= nl && r >= nr)
            return val;
        if (l >= nr || nl >= r)
            return 0;
        propagate();
        return pl->query(l, r) + pr->query(l, r);
    }
};

pointer.cpp

struct Tree {
    Tree *pl, *pr;
    int nl = 0, nr = 0, val = 0;

    void updateVal() { val = pl->val + pr->val; }

    Tree(int l, int r, int A[]) {
        nl = l, nr = r;
        if (nl + 1 == nr) {
            val = A[nl];
            return;
        }
        pl = new Tree(nl, nl + nr >> 1, A);
        pr = new Tree(nl + nr >> 1, nr, A);
        updateVal();
    }
    void modify(int p, int x) {
        if (p < nl || nr <= p) {
            return;
        }
        if (nl + 1 == nr) {
            val = x;
            return;
        }
        pl->modify(p, x);
        pr->modify(p, x);
        updateVal();
    }
    int query(int l, int r) {
        if (l <= nl && r >= nr)
            return val;
        if (l >= nr || nl >= r)
            return 0;
        return pl->query(l, r) + pr->query(l, r);
    }
};

range modify point query.cpp

int seg[2 * MAXN];

void modify(int l, int r, int val) {
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            seg[l++] += val;
        if (r & 1)
            seg[--r] += val;
    }
}

int query(int p) {
    int res = 0;
    for (p += N; p > 0; p >>= 1)
        res += seg[p];
    return res;
}

range query point modify (standard).cpp

int seg[2 * MAXN];
void build() {
    for (int i = N - 1; i >= 0; i--)
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

void modify(int p, int val) {
    for (seg[p += N] = val; p > 0; p >>= 1)
        seg[p >> 1] = seg[p] + seg[p ^ 1];
}

int query(int l, int r) {
    int res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += seg[l++];
        if (r & 1)
            res += seg[--r];
    }
    return res;
}

Lazy Segtrees form a semi-ring, where update=multiplication, query=addition. We need that U(Q(l), Q(r)) = Q(U(l), U(r))