基础线段树模板题

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
using namespace std;
const int N=100005;
int n,m,k,s,t,v[N],ty;
struct node{
	ll sum,sign;
}a[N*4];
void update(int p){
	a[p].sum=a[p<<1].sum+a[p<<1|1].sum;
}
void build(int p,int l,int r){
	if (l==r) {
		a[p].sum=v[l];
		return;
	}
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
}
void down(int p,int l,int r){
	a[p<<1].sum+=(mid-l+1)*a[p].sign;
	a[p<<1].sign+=a[p].sign;
	a[p<<1|1].sum+=(r-mid)*a[p].sign;
	a[p<<1|1].sign+=a[p].sign;
	a[p].sign=0;
}
void add(int p,int l,int r,int s,int t,ll k){//s到t增加k 
	//当前区间被完整覆盖，更新sum和，并打上标记 
	if (l>=s && r<=t){ 
		a[p].sum+=(r-l+1)*k;
		a[p].sign+=k;
		return;
	}
	//当前节点存在标记且要访问该节点的子节点了，下传标记 
	if (a[p].sign) down(p,l,r);
	if (s<=mid) add(p<<1,l,mid,s,t,k);
	if (t>mid) add(p<<1|1,mid+1,r,s,t,k);
	//更新当前节点信息 
	update(p);
}

ll query(int p,int l,int r,int s,int t){//查询s到t的和 
	if (l>=s && r<=t){
		return a[p].sum;
	}
	//下传标记 
	if (a[p].sign) down(p,l,r);
	ll ans=0;
	if (s<=mid) ans+=query(p<<1,l,mid,s,t);
	if (t>mid) ans+=query(p<<1|1,mid+1,r,s,t); 
	return ans;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i)	cin>>v[i];
	build(1,1,n);
	for (int i=1;i<=m;++i){
		cin>>ty>>s>>t;
		if (ty==1){
			cin>>k;
			add(1,1,n,s,t,k);
		}
		else cout<<query(1,1,n,s,t)<<endl;
	}
} 

#include<bits/stdc++.h>
#define INF 0x3fffffff
#define ll long long
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl;
#define MAX 100010
using namespace std;
ll n, m, s[MAX], sum[MAX << 2], Add[MAX << 2], f, a, b, c;
void pushup(ll rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(ll l, ll r, ll rt) {
    if(l == r) {
        sum[rt] = s[l];
        return;
    }
    ll m = (r + l) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}
void PushDown(ll rt, ll ln, ll rn) {
    if(Add[rt]) {
        Add[rt << 1] += Add[rt];
        Add[rt << 1 | 1] += Add[rt];
        sum[rt << 1] += Add[rt] * ln;
        sum[rt << 1 | 1] += Add[rt] * rn;
        Add[rt] = 0;
    }
}
void update(ll L, ll R, ll C, ll l, ll r, ll rt) {
    if(L <= l && r <= R) {
        sum[rt] += C * (r - l + 1);
        Add[rt] += C;
        return ;
    }
    ll m = (l + r) >> 1;
    PushDown(rt, m - l + 1, r - m);
    if(L <= m)
        update(L, R, C, l, m, rt << 1);
    if(R >  m)
        update(L, R, C, m + 1, r, rt << 1 | 1);
    pushup(rt);
}
 
ll query(ll L, ll R, ll l, ll r, ll rt) {
    if(L <= l && r <= R) {
        return sum[rt];
    }
    ll m = (r + l) >> 1;
    PushDown(rt, m - l + 1, r - m);
    ll ans = 0;
    if(L <= m)
        ans += query(L, R, l, m, rt << 1);
    if(R > m)
        ans += query(L, R, m + 1, r, rt << 1 | 1);
    return ans;
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> s[i];
    build(1, n, 1);
    for(int i = 0; i < m; i++) {
        cin >> f;
        if(f == 1) {
            cin >> a >> b >> c;
            update(a, b, c, 1, n, 1);
        } else {
            cin >> a >> b;
            cout << query(a, b, 1, n, 1) << endl;
        }
    }
    return 0;
}