C++ – 线段树

long long s[maxn * 4];
long long lz[maxn * 4];

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

inline void push_up(int rt) {
    s[rt] = s[ls(rt)] + s[rs(rt)];
    s[rt] %= mod;
}

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

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

void upd(int rt, int l, int r, int tl, int tr, long long k) {
    if (tl > tr) return;
    if (l >= tl && r <= tr) {
        s[rt] += k * (r - l + 1);
        s[rt] %= mod;
        lz[rt] += k;
        return;
    }
    push_down(rt, r - l + 1);
    int 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);
}

long long ask(int rt, int l, int r, int tl, int tr) {
    if (tl > tr) return 0l;
    if (l == tl && r == tr)
        return s[rt];
    push_down(rt, r - l + 1);
    int 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;
}