线段树

发表于 | 更新于 | 阅读次数：

最近在学线段树。

线段树具有树的结构特征，对于每一个子节点而言，都表示整个序列中的一段子区间；对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。因此线段树可以处理很多符合结合律的操作。

下面是区间修改区间求值的程序$($我懒得打单点修改区间求值和区间修改单调求值了23333$)$。

代码

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
#include<bits/stdc++.h>
#define N 100000
#define ll long long
using namespace std;
ll n,m,l,r,v,k;
ll a[N+5],sum[4*N+5],add[4*N+5];
void build(ll k,ll l,ll r){
	if(l==r){
		sum[k]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
void Add(ll k,ll l,ll r,ll v){
	add[k]+=v;
	sum[k]+=v*(r-l+1);
}
void pushdown(ll k,ll l,ll r,ll mid){
	if(!add[k])return;
	Add(k<<1,l,mid,add[k]);
	Add(k<<1|1,mid+1,r,add[k]);
	add[k]=0;
}
ll query_sum(ll k,ll l,ll r,ll x,ll y){
	if(l>=x&&r<=y)return sum[k];
	ll mid=(l+r)>>1,res=0;
	pushdown(k,l,r,mid);
	if(x<=mid)res+=query_sum(k<<1,l,mid,x,y);
	if(y>mid)res+=query_sum(k<<1|1,mid+1,r,x,y);
	return res;
}
void change(ll k,ll l,ll r,ll x,ll y,ll v){
	if(l>=x&&r<=y){
		Add(k,l,r,v);
		return;
	}
	ll mid=(l+r)>>1;
	pushdown(k,l,r,mid);
	if(x<=mid)change(k<<1,l,mid,x,y,v);
	if(y>mid)change(k<<1|1,mid+1,r,x,y,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%lld",&k);
		switch(k){
			case 1:{
				scanf("%lld%lld%lld",&l,&r,&v);
				change(1,1,n,l,r,v);
				break;
			}
			case 2:{
				scanf("%lld%lld",&l,&r);
				printf("%lld\n",query_sum(1,1,n,l,r));
				break;
			}
		}
	}
	return 0;
}