luoguP4868 Preprefix sum

https://www.luogu.org/problemnew/show/P4868

线段树上加等差数列，基础区间修改单点查询

等差数列具有可加性，当在同一段区间内时，首项相加公差相加即可

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T &f) {
    f = 0; T fu = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}
    while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}
    f *= fu;
}

typedef long long ll;
const int N = 100000 + 10;

struct Tree {
    ll val[N << 2], sx[N << 2], gc[N << 2];
    
    void update(int u) {
        val[u] = val[u << 1] + val[u << 1 | 1];
    }
    
    void pushdown(int u, int l, int r) {
        if(sx[u] || gc[u]) {
            int mid = (l + r) >> 1;
            ll llen = (mid - l + 1);
            ll rlen = (r - mid);
            val[u << 1] += (sx[u] + sx[u] + gc[u] * (llen - 1)) * llen / 2ll;
            val[u << 1 | 1] += (sx[u] * 2 + gc[u] * llen * 2 + gc[u] * (rlen - 1)) * rlen / 2ll;
            sx[u << 1] += sx[u]; sx[u << 1 | 1] += sx[u] + gc[u] * llen;
            gc[u << 1] += gc[u]; gc[u << 1 | 1] += gc[u];
            sx[u] = gc[u] = 0;
        }
    }
    
    void change(int u, int l, int r, int L, int R, ll x, ll y) {
        if(l <= L && R <= r) {
            int len = (R - L + 1); x += (L - l) * y;
            val[u] += (x + x + (len - 1) * y) * len / 2ll;
            sx[u] += x; gc[u] += y;
            return;
        }
        pushdown(u, L, R);
        int mid = (L + R) >> 1;
        if(mid >= l) change(u << 1, l, r, L, mid, x, y);
        if(mid + 1 <= r) change(u << 1 | 1, l, r, mid + 1, R, x, y);
        update(u);
    }
    
    ll query(int u, int l, int r, int L, int R) {
        if(l <= L && R <= r) return val[u];
        pushdown(u, L, R); int mid = (L + R) >> 1;
        ll ans = 0;
        if(mid >= l) ans += query(u << 1, l, r, L, mid);
        if(mid + 1 <= r) ans += query(u << 1 | 1, l, r, mid + 1, R);
        return ans;
    }
}p;

char c[12];
int w[N];
int n, m;

int main() {
    read(n); read(m);
    for(int i = 1; i <= n; i++) {
        read(w[i]);
        p.change(1, i, n, 1, n, w[i], w[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%s", c + 1);
        if(c[1] == 'Q') {
            int a; read(a);
            printf("%lld
", p.query(1, a, a, 1, n));
        } else {
            int a, b; read(a); read(b);
            p.change(1, a, n, 1, n, -w[a], -w[a]);
            w[a] = b;
            p.change(1, a, n, 1, n, w[a], w[a]);
        }
    }
    return 0;
}