题目类型 线段树 - 区间修改
题目意思
给出最多100000个数 现在有最多100000个操作
操作1 把 区间 [Ｌ,Ｒ]中的数加上一个数c
操作2 询问区间 [Ｌ,Ｒ]中的数的和是多少
解题方法
区间修改的线段树
注意懒惰标记的使用就行了
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mid ((l+r)>>1)
typedef long long LL;
const int maxn = 1e5 + 10;
LL sum[maxn*4], add[maxn*4];
int A[maxn];
void build(int rt, int l, int r) {
if(l == r) {
sum[rt] = A[l];
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
sum[rt] = sum[ls] + sum[rs];
}
void pushdown(int rt, int l, int r) {
if(l != r) {
if(add[rt]) {
sum[ls] += (mid - l + 1) * add[rt]; add[ls] += add[rt];
sum[rs] += (r - mid) * add[rt]; add[rs] += add[rt];
add[rt] = 0;
}
}
}
void update(int rt, int l, int r, int L, int R, int c) {
pushdown(rt, l, r);
if(l == L && r == R) {
sum[rt]+= (r-l+1)*c;
add[rt] = c;
return ;
}
if(R <= mid) update(ls, l, mid, L, R, c);
else if(L > mid) update(rs, mid + 1, r, L, R, c);
else update(ls, l, mid, L, mid, c), update(rs, mid + 1, r, mid + 1, R, c);
sum[rt] = sum[ls] + sum[rs];
}
LL query(int rt, int l, int r, int L, int R) {
pushdown(rt, l, r);
if(l == L && r == R) return sum[rt];
if(R <= mid) return query(ls, l, mid, L, R);
else if(L > mid) return query(rs, mid + 1, r, L, R);
else return query(ls, l, mid, L, mid) + query(rs, mid + 1, r, mid + 1, R);
sum[rt] = sum[ls] + sum[rs];
}
int main() {
freopen("in", "r", stdin);
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
for( int i=0; i<n; i++ ) scanf("%d", &A[i]);
build(1, 0, n);
for( int i=0; i<m; i++ ) {
char str[10];
scanf("%s", str);
if(str[0] == 'Q') {
int l, r;
scanf("%d%d", &l, &r);
LL ans = query(1, 0, n, l-1, r-1);
cout<<ans<<endl;
}
else {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
update(1, 0, n, l-1, r-1, c);
}
}
}
return 0;
}