一种线段树卡空间方法

$4N\to2N$

原题

#include<functional>
#include<iostream>
using namespace std;
using func = const function<void(int)>&;
using ll = long long;

const int N = 1e5, T = N*2+2;
int n, a[N], le[T], re[T]; ll w[T], tg[T];
#define ls m*2
#define rs m*2|1
void bd(int u=1, int L=1, int R=n) {
    le[u] = L, re[u] = R; int m = L + R >> 1;
    if (L == R) w[u] = a[L-1];
    else bd(ls, L, m), bd(rs, m+1, R), w[u] = w[ls]+w[rs];
}
#define L le[u]
#define R re[u]
void cg(int u, int k) { tg[u] += k, w[u] += (R-L+1)*k; }
void md(int l, int r, func f, int u=1) {
    if (l <= L && R <= r) return f(u);
    int m = L + R >> 1;
    cg(ls, tg[u]), cg(rs, tg[u]), tg[u] = 0;
    if (l <= m) md(l, r, f, ls);
    if (r > m) md(l, r, f, rs);
    w[u] = w[ls] + w[rs];
}
void ad(int l, int r, int k) { md(l, r, [&](int u){cg(u, k);}); }
ll qr(int l, int r) { ll sm = 0; md(l, r, [&](int u){sm += w[u];}); return sm; }
int main() {
#ifdef _TEST
    freopen("a.in", "r", stdin);
#endif
    int m, op, x, y, k; cin >> n >> m;
    for (int i=0; i<n; i++) cin >> a[i];
    for (bd(); m--;) if (cin>>op>>x>>y, op == 2) printf("%lld\n", qr(x, y));
        else cin >> k, ad(x, y, k);
    return 0;
}

原理大概是用 m*2和 *2+1代替 u*2,u*2+1 为左儿子下标。

考虑不同节点的 $m$ 一定不同，因此 $2m,2m+1$ 可以做到与儿子一一对应。