Lazy Segment Tree

O(log n) per operation

Segment tree with lazy propagation: range updates and range queries, both logarithmic. This version does range add + range sum. To change it, adjust apply() (how an update hits a node) and the two combine lines. The recursive structure is the part worth memorizing.

// use it on

CSES: Range Update Queries ↗

Range add, point read. A point read is query(i, i), so the template applies directly.

// the code

struct LazySegTree {  // range add, range sum on [l, r]
    int n;
    vector<long long> t, lz;
    LazySegTree(int n) : n(n), t(4 * n, 0), lz(4 * n, 0) {}
    void apply(int x, int l, int r, long long v) {
        t[x] += v * (r - l + 1);
        lz[x] += v;
    }
    void push(int x, int l, int r) {
        if (lz[x] == 0) return;
        int m = (l + r) / 2;
        apply(2 * x, l, m, lz[x]);
        apply(2 * x + 1, m + 1, r, lz[x]);
        lz[x] = 0;
    }
    void update(int x, int l, int r, int ql, int qr, long long v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) return apply(x, l, r, v);
        push(x, l, r);
        int m = (l + r) / 2;
        update(2 * x, l, m, ql, qr, v);
        update(2 * x + 1, m + 1, r, ql, qr, v);
        t[x] = t[2 * x] + t[2 * x + 1];
    }
    long long query(int x, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return t[x];
        push(x, l, r);
        int m = (l + r) / 2;
        return query(2 * x, l, m, ql, qr) +
               query(2 * x + 1, m + 1, r, ql, qr);
    }
    void update(int l, int r, long long v) { update(1, 0, n - 1, l, r, v); }
    long long query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

// more range queries

Segment Tree Fenwick Tree (BIT)Sparse Table