前言

线段树就是ST啊(Segment Tree)，其实我在玩梗233333

1.线段树思想

在区间求和，区间求最值，区间修改的时候，如果遍历一遍，每次都需要O(n)的时间复杂度，加起来就是O($n^2$)的时间复杂度，很慢对吧，所以我们需要O($n*log_n$)的线段树来实现。
把区间二分二分再二分，然后用树来存储与维护，就像把线段放在树里一样。

2.线段树模板

建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct T{
	int l,r,ls,rs;     //l是左端点,r是右端点,ls是左儿子,rs是右儿子
	int sum,ma,mark;   //sum是区间和,ma是区间最值（以最大值为例）,mark是lazy标记
}t[M];               //M用define或者const int来定义，一般赋一个很大的值
int tot=1;           //计数器
void build(int root,int l,int r)
{
	t[root].l=l;t[root].r=r;
	if(l==r) 
	{
		t[root].sum=a[i];      //a[i]是读入的区间内的值
		t[root].ma=a[i];
		return ;
	}
	int mid=(l+r)/2;
	t[root].ls=++tot;build(t[root].ls,l,mid);
	t[root].rs=++tot;build(t[root].rs,mid+1,r);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
	t[root].ma=max(t[t[root].ls].ma,t[t[root].rs].ma);
}

区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void change(int x,int l,int r,int d)
{
	if(l<=t[x].l&&r>=t[x].r)
	{
		t[x].mark+=d;
		t[x].sum+=d*(t[x].r-t[x].l+1);
		t[x].ma+=d;
		return ;
	}
	push_(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) change(t[x].ls,l,r,d);
	if(r>mid)  change(t[x].rs,l,r,d); 
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;	
	t[x].ma=max(t[t[x].ls].ma,t[t[x].rs].ma);
}

区间求和查询

1
2
3
4
5
6
7
8
9
10
11
12
13
int query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		return t[x].sum;
	}
	push_(x);
	int ans=0;
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) ans+=query(t[x].ls,l,r);
	if(r>mid)  ans+=query(t[x].rs,l,r);
	return ans;
}

区间求最值查询（以最大值为例）

1
2
3
4
5
6
7
8
9
10
11
12
int compare(int x,int l,int r)
{
	if(t[x].l>=l&&t[x].r<=r)
	{
		return t[x].ma;
	}
	push_(x);
	int mid=(t[x].l+t[x].r)/2,maxx=0;
	if(l<=mid) maxx=max(maxx,compare(t[x].ls,l,r));
	if(r>mid)  maxx=max(maxx,compare(t[x].rs,l,r));
	return maxx;
}

lazy标记操作

1
2
3
4
5
6
7
8
void push_(int x)
{
	if(t[x].mark==0) return ;
	int M=t[x].mark,L=t[x].ls,r=t[x].rs;
	t[L].mark+=M; t[L].sum+=M*(t[L].r-t[L].l+1); t[L].ma+=M;
	t[R].mark+=M; t[R].sum+=M*(t[R].r-t[R].l+1); t[R].ma+=M;
	t[x].mark=0;
}

3.线段树模板题

【题目链接】
洛谷【3372】
【题目大意】
线段树区间求和&&单点修改
【输入格式】
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k；
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和。
【输出格式】
输出包含若干行整数，即为所有操作2的结果。
【输入样例】

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

【输出样例】

11
8
20

【程序】

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
88
89
90
#include<cstdio>
#include<iostream>
#define M 2005000
using namespace std;
int n,m,q;
long long a[M];
struct T{
	int l,r,ls,rs;
	long long sum,mark;
}t[M];
int tot=1;
void build(int x,int l,int r)
{
	t[x].l=l;t[x].r=r;
	if(l==r)
	{
		t[x].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	t[x].ls=++tot;build(t[x].ls,l,mid);
	t[x].rs=++tot;build(t[x].rs,mid+1,r);
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
void push_(int x)
{
	if(t[x].mark==0) return ;
	int l=t[x].ls,r=t[x].rs,ma=t[x].mark;
	t[l].mark+=ma;	t[l].sum+=ma*(t[l].r-t[l].l+1);
	t[r].mark+=ma;	t[r].sum+=ma*(t[r].r-t[r].l+1);
	t[x].mark=0;
}
void change(int x,int l,int r,int k)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		t[x].mark+=k;
		t[x].sum+=k*(t[x].r-t[x].l+1);
		return ;
	}
	push_(x);
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) change(t[x].ls,l,r,k);
	if(mid<r)  change(t[x].rs,l,r,k);
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
long long query(int x,int l,int r)
{
	if(l<=t[x].l&&t[x].r<=r)
	{
		return t[x].sum;
	}
	push_(x);
	long long ans=0;
	int mid=(t[x].l+t[x].r)/2;
	if(l<=mid) ans+=query(t[x].ls,l,r);
	if(mid<r)  ans+=query(t[x].rs,l,r);
	return ans;
}
int main()
{
//	freopen("tree.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	int x,y,k;
	while(m--)
	{
		scanf("%d",&q);
		if(q==1)
		{
			scanf("%d%d%d",&x,&y,&k);
			change(1,x,y,k);
		}
		else
		{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}
	return 0;
}