线段树

发表于

线段树基于分治的思想 是一颗二叉树

可以用于对区间信息的动态查询修改

线段树的每一个节点都代表一个区间

线段树具有唯一的根节点，代表整个范围 而每个叶子节点代表一个长度为1的区间

在保存线段树时 数组长度要不小于4N

线段树的单点修改,查询的复杂度O(logN)

在修改时我们要延迟标记。对任意节点的修改都延迟到在后续操作中递归进入它的父节点时再执行。

以上是线段树的主要内容，望有所参考

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
#include <cstdio>
#define ll long long
using namespace std;
int n,m;
ll a[100001],sum[100001*4],left[100001*4],right[100001*4],add[100001*4];
void build(int p,int l,int r){
	left[p]=l;right[p]=r;
	if(l==r){
		sum[p]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	sum[p]=sum[p*2]+sum[p*2+1];
}
void spread(int p){
	if(add[p]){
		sum[p*2]+=add[p]*(right[p*2]-left[p*2]+1);
		sum[p*2+1]+=add[p]*(right[p*2+1]-left[p*2+1]+1);
		add[p*2]+=add[p];
		add[p*2+1]+=add[p];
		add[p]=0;
	}
}
void change(int p,int l,int r,int d){
	if(l<=left[p]&&right[p]<=r){
		sum[p]+=(long long)d*(right[p]-left[p]+1);
		add[p]+=d;
		return;
	}
	spread(p);
	int mid=(left[p]+right[p])/2;
	if(l<=mid)change(p*2,l,r,d);
	if(r>mid)change(p*2+1,l,r,d);
	sum[p]=sum[p*2]+sum[p*2+1];
}
ll ask(int p,int l,int r){
	if(l<=left[p]&&right[p]<=r)return sum[p];
	spread(p);
	int mid=(left[p]+right[p])/2;
	ll val=0;
	if(l<=mid)val+=ask(p*2,l,r);
	if(r>mid)val+=ask(p*2+1,l,r);
	return val;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
		int tmp,l,r,d;
		scanf("%d%d%d",&tmp,&l,&r);
		if(tmp==1){
			scanf("%d",&d);
			change(1,l,r,d);
		}
		else printf("%lld\n",ask(1,l,r));
	}
	return 0;
}