题解 | #【模板】动态区间和Ⅱ ‖ 区间修改 + 区间查询#

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

struct SegTree {
    int n; vector<i64> sum, lz;
    SegTree(int n=0): n(n) { sum.assign(4*n+4, 0); lz.assign(4*n+4, 0); }
    void build(int idx, int l, int r, const vector<i64>& a){
        if(l==r){ sum[idx]=a[l]; return; }
        int mid=(l+r)>>1; build(idx<<1,l,mid,a); build(idx<<1|1,mid+1,r,a);
        sum[idx]=sum[idx<<1]+sum[idx<<1|1];
    }
    void apply(int idx, int l, int r, i64 v){ sum[idx]+=v*(r-l+1); lz[idx]+=v; }
    void push(int idx, int l, int r){ if(lz[idx]==0) return; int mid=(l+r)>>1; apply(idx<<1,l,mid,lz[idx]); apply(idx<<1|1,mid+1,r,lz[idx]); lz[idx]=0; }
    void range_add(int idx, int l, int r, int ql, int qr, i64 v){
        if(ql<=l && r<=qr){ apply(idx,l,r,v); return; }
        push(idx,l,r); int mid=(l+r)>>1;
        if(ql<=mid) range_add(idx<<1,l,mid,ql,qr,v);
        if(qr>mid)  range_add(idx<<1|1,mid+1,r,ql,qr,v);
        sum[idx]=sum[idx<<1]+sum[idx<<1|1];
    }
    i64 range_sum(int idx, int l, int r, int ql, int qr){
        if(ql<=l && r<=qr) return sum[idx];
        push(idx,l,r); int mid=(l+r)>>1; i64 ans=0;
        if(ql<=mid) ans+=range_sum(idx<<1,l,mid,ql,qr);
        if(qr>mid)  ans+=range_sum(idx<<1|1,mid+1,r,ql,qr);
        return ans;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; if(!(cin>>n>>m)) return 0;
    vector<i64> a(n+1); for(int i=1;i<=n;i++) cin>>a[i];
    SegTree st(n); st.build(1,1,n,a);
    while(m--){
        int op; cin>>op;
        if(op==1){ int l,r; i64 x; cin>>l>>r>>x; st.range_add(1,1,n,l,r,x); }
        else{ int l,r; cin>>l>>r; cout<<st.range_sum(1,1,n,l,r)<<'\n'; }
    }
    return 0;
}

import java.io.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0,l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
        long nextLong() throws IOException { int c; long s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    static class SegTree {
        int n; long[] sum, lz;
        SegTree(int n){ this.n=n; sum=new long[4*n+4]; lz=new long[4*n+4]; }
        void build(int idx,int l,int r,int[] a){ if(l==r){ sum[idx]=a[l]; return; } int m=(l+r)>>1; build(idx<<1,l,m,a); build(idx<<1|1,m+1,r,a); sum[idx]=sum[idx<<1]+sum[idx<<1|1]; }
        void apply(int idx,int l,int r,long v){ sum[idx]+=v*(r-l+1); lz[idx]+=v; }
        void push(int idx,int l,int r){ if(lz[idx]==0) return; int m=(l+r)>>1; apply(idx<<1,l,m,lz[idx]); apply(idx<<1|1,m+1,r,lz[idx]); lz[idx]=0; }
        void add(int idx,int l,int r,int ql,int qr,long v){ if(ql<=l&&r<=qr){ apply(idx,l,r,v); return; } push(idx,l,r); int m=(l+r)>>1; if(ql<=m) add(idx<<1,l,m,ql,qr,v); if(qr>m) add(idx<<1|1,m+1,r,ql,qr,v); sum[idx]=sum[idx<<1]+sum[idx<<1|1]; }
        long sumQ(int idx,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return sum[idx]; push(idx,l,r); int m=(l+r)>>1; long ans=0; if(ql<=m) ans+=sumQ(idx<<1,l,m,ql,qr); if(qr>m) ans+=sumQ(idx<<1|1,m+1,r,ql,qr); return ans; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[n+1];
        for(int i=1;i<=n;i++) a[i]=fs.nextInt();
        SegTree st = new SegTree(n);
        st.build(1,1,n,a);
        StringBuilder out = new StringBuilder();
        while(m-- > 0){
            int op = fs.nextInt();
            if(op==1){ int l=fs.nextInt(), r=fs.nextInt(); long x=fs.nextLong(); st.add(1,1,n,l,r,x); }
            else { int l=fs.nextInt(), r=fs.nextInt(); out.append(st.sumQ(1,1,n,l,r)).append('\n'); }
        }
        System.out.print(out.toString());
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
a = [0]*(n+1)
for i in range(1, n+1):
    a[i] = int(next(it))

# 区间版树状数组：两个 BIT 支持 range add & range sum
BIT1 = [0]*(n+1)
BIT2 = [0]*(n+1)

def _add(B, i, v):
    while i <= n:
        B[i] += v
        i += i & -i

def _sum(B, i):
    s = 0
    while i > 0:
        s += B[i]
        i -= i & -i
    return s

def range_add(l, r, v):
    _add(BIT1, l, v); _add(BIT1, r+1, -v)
    _add(BIT2, l, v*(l-1)); _add(BIT2, r+1, -v*r)

def prefix_sum(x):
    return _sum(BIT1, x)*x - _sum(BIT2, x)

def range_sum(l, r):
    if l > r:
        l, r = r, l
    return prefix_sum(r) - prefix_sum(l-1)

# 用单点加构建初始数组
for i in range(1, n+1):
    range_add(i, i, a[i])

out_lines = []
for _ in range(m):
    op = int(next(it))
    if op == 1:
        l = int(next(it)); r = int(next(it)); x = int(next(it))
        range_add(l, r, x)
    else:
        l = int(next(it)); r = int(next(it))
        out_lines.append(str(range_sum(l, r)))

sys.stdout.write('\n'.join(out_lines))