C++ – 线段树 Segment Tree

struct segment_tree_t {
    lli n;
    vector<lli> te;
    vector<lli> lz;

    segment_tree_t(lli n) : n(n), te(n << 2, 0), lz(n << 2, 0) { }

    lli ls(lli x) { return x << 1; }
    lli rs(lli x) { return x << 1 | 1; }

    void push_up(lli rt) {
        te[rt] = te[ls(rt)] + te[rs(rt)];
        te[rt] %= mod;
    }

    void push_down(lli rt, lli le) {
        if (lz[rt]) {
            lz[ls(rt)] += lz[rt];
            lz[rs(rt)] += lz[rt];
            te[ls(rt)] += lz[rt] * (le - (le >> 1));
            te[rs(rt)] += lz[rt] * (le >> 1);
            te[ls(rt)] %= mod;
            te[rs(rt)] %= mod;
            lz[rt] = 0;
        }
    }

    void build(lli* arr) { build(1, 1, n, arr); }

    void build(lli rt, lli l, lli r, lli* arr) {
        if (l == r) {
            te[rt] = arr[l];
            te[rt] %= mod;
            return;
        }
        lli mid = (l + r) >> 1;
        build(ls(rt), l, mid, arr);
        build(rs(rt), mid + 1, r, arr);
        push_up(rt);
    }

    void upd(lli tl, lli tr, lli k) { upd(1, 1, n, tl, tr, k); }

    void upd(lli rt, lli l, lli r, lli tl, lli tr, lli k) {
        if (tl > tr) return;
        if (l >= tl && r <= tr) {
            te[rt] += k * (r - l + 1);
            te[rt] %= mod;
            lz[rt] += k;
            return;
        }
        push_down(rt, r - l + 1);
        lli mid = (l + r) >> 1;
        if (tl <= mid) upd(ls(rt), l, mid, tl, tr, k);
        if (tr > mid) upd(rs(rt), mid + 1, r, tl, tr, k);
        push_up(rt);
    }

    lli ask(lli tl, lli tr) { return ask(1, 1, n, tl, tr); }

    lli ask(lli rt, lli l, lli r, lli tl, lli tr) {
        if (tl > tr) return 0;
        if (l == tl && r == tr)
            return te[rt];
        push_down(rt, r - l + 1);
        lli mid = (l + r) >> 1;
        if (tr <= mid) return ask(ls(rt), l, mid, tl, tr);
        if (tl > mid) return ask(rs(rt), mid + 1, r, tl, tr);
        return (ask(ls(rt), l, mid, tl, mid) + ask(rs(rt), mid + 1, r, mid + 1, tr)) % mod;
    }
};