东方博宜OJ 2390：区间修改与查询 ← 线段树-拓冰建站

【题目来源】
https://oj.czos.cn/p/2390

【题目描述】
给定由 N 个整数构成的数列，再给定 M 条指令，每条指令可能是如下两种之一：
1. C l r d，表示将区间 [l,r] 之间的每个数都加上整数 d；
2. Q l r，表示询问区间 [l,r] 之间所有数的和；
对于每次询问，请输出对应的和。

【输入格式】
第 1 行有 2 个整数 N 和 M。
第 2 行有 N 个整数，空格隔开。
接下来 M 行，每行读入一条题目描述的指令。

【输出格式】
输出若干行，每行一个整数，代表了对于每次询问输出的结果。

【输入样例】
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

【输出样例】
4
55
9
15

【数据范围】
1≤N,M≤10^5，1≤l,r≤N，-10000≤d≤10000,
读入的 N 个整数的值在[-10^9,10^9]范围。

【算法分析】
● 本文代码与“洛谷 P3372：线段树 1”代码基本一样。详见：https://blog.csdn.net/hnjzsyjyj/article/details/152356965

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1e5+5;
LL a[N];struct Node {int le,ri;LL sum,k;
} tr[N*4];void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}void addtag(int u,LL k) {tr[u].sum+=(tr[u].ri-tr[u].le+1)*k;tr[u].k+=k;
}void pushdown(int u) {if(tr[u].k) {addtag(u<<1,tr[u].k);addtag(u<<1|1,tr[u].k);tr[u].k=0;}
}void build(int u,int le,int ri) {tr[u]= {le,ri};if(le==ri) tr[u].sum=a[le];else {int mid=le+ri>>1;build(u<<1,le,mid);build(u<<1|1,mid+1,ri);pushup(u);}
}LL query(int u,int le,int ri) {if(tr[u].le>=le && tr[u].ri<=ri) return tr[u].sum;else if(tr[u].le>ri || tr[u].ri<le) return 0;else {pushdown(u);return query(u<<1,le,ri)+query(u<<1|1,le,ri);}
}void update(int u,int le,int ri,LL k) {if(tr[u].le>=le && tr[u].ri<=ri) addtag(u,k);else if(tr[u].le>ri || tr[u].ri<le) return;else {pushdown(u);update(u<<1,le,ri,k);update(u<<1|1,le,ri,k);pushup(u);}
}int main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) {cin>>a[i];}build(1,1,n);LL k;char op;int x,y;while(m--) {cin>>op;if(op=='C') {cin>>x>>y>>k;update(1,x,y,k);} else {cin>>x>>y;cout<<query(1,x,y)<<endl;}}
}/*
in:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4out:
4
55
9
15
*/