洛谷 P3372 【模板】线段树 1

PS：如果读过题了可以跳过题目描述直接到题解部分
提交链接：洛谷P3372 【模板】线段树 1

题目

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n,m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 $[x,y]$ 内每个数加上 $k$。
2. 2 x y：输出区间 $[x,y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
1
2
3
4
5
6
7

样例输出 #1

11
8
20
1
2
3

提示

对于 $30\%$ 的数据：$n\le 8$，$m\le 10$。
对于 $70\%$ 的数据：$n\le {10}^3$，$m\le {10}^4$。
对于 $100\%$ 的数据：$1\le n,m\le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

代码实现

100pts

//洛谷P3372 【模板】线段树 1
#pragma GCC optimize(3)
#include
#include
using namespace std;
int n,m;
long long a[100010];
long long b[400010];
long long tag[400010];
int opt;
int x,y;
long long k;

void build(int rt,int l,int r){
	if(l==r){
		b[rt]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	b[rt]=b[rt<<1]+b[rt<<1|1];
}

void push(int rt,int ll,int rr){
	tag[rt<<1]+=tag[rt];
	tag[rt<<1|1]+=tag[rt];
	int mid=ll+rr>>1;
	b[rt<<1]+=tag[rt]*(mid-ll+1);
	b[rt<<1|1]+=tag[rt]*(rr-mid);
	tag[rt]=0;
}

void change(int rt,int ll,int rr,int l,int r,long long k){
	if(ll>=l&&rr<=r){
		tag[rt]+=k;
		b[rt]+=k*(rr-ll+1);
		return;
	}
	push(rt,ll,rr);
	int mid=ll+rr>>1;
	if(l<=mid){
		change(rt<<1,ll,mid,l,r,k);
	}
	if(r>mid){
		change(rt<<1|1,mid+1,rr,l,r,k);
	}
	b[rt]=b[rt<<1]+b[rt<<1|1];
}

long long query(int rt,int ll,int rr,int l,int r){
	if(ll>=l&&rr<=r){
		return b[rt];
	}
	if(tag[rt]){
		push(rt,ll,rr);
	}
	int mid=ll+rr>>1;
	long long ans=0;
	if(l<=mid){
		ans+=query(rt<<1,ll,mid,l,r);
	}
	if(r>mid){
		ans+=query(rt<<1|1,mid+1,rr,l,r);
	}
	return ans;
}

int main(){
	register int i;
	cin>>n>>m;
	for(i=1;i<=n;++i){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		cin>>opt>>x>>y;
		if(opt&1){
			cin>>k;
			change(1,1,n,x,y,k);
		}
		else{
			cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87