线段树模板

发表于 | 分类于

lyd 版

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1050;		//整个大小	 
int a[N];
struct SegmentTree{		//线段树结构体，代表每一个节点，左区间，右区间，还有这个区间的特征值(如最大值，最小值)
					//当 t[ ].l == t[ ].r true时代表一个点 
	int l, r, dat;		
}t[N * 4]; 		//开4倍空间，1. 总数为非2 ^ n 时 logn层即倒数第二层，最后一层还剩了一些节点  
						  // 2. 总数为2 ^ n时为最后一层，还是需要多开一倍(一层),来包涵所有情况
void build(int p, int l ,int r)		//节点下标，左右区间 
{
	t[p].l = l, t[p].r = r;		//建树时记录这个节点代表的区间 
	if(l == r)	{ t[p].dat = a[l]; return ; }	//如果变成了一个点节点对应原数组值(节点下标类似于堆的储存，为四倍长度) 
	int mid = l + r >> 1;	//建树的区间不断分治思想进行划分，左子树 、右子树开始建树 
	build(p * 2, l, mid);		//建立左子树 
	build(p * 2 + 1, mid + 1, r);		//建立右子树 
	t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);		//根节点为左右节点的最大值 
}
//树枝一定有两个叶子节点
//证明: 假设树枝只有一个叶子节点，这一个子节点(即叶子)为[x, x]那么往上推，根节点为叶子区间取并，那么根节点也为[x, x]，而根据build函数，l == r true时
	//是不会执行子节点的build ，与有子节点矛盾 ，故假设不成立 

void change(int p, int x, int v)	//节点，修改a[]数组中第几个数，要修改为的值 
{
	if(t[p].l == t[p].r){ t[p].dat = v; return ; }	//这个节点区间范围为1(说明找到改的目标值，然后进行 回溯 ，对相关区间的进行更新)	 (并且这个节点没有子节点) 
	int mid = t[p].l + t[p].r >> 1;		 //取节点区间的中点值 
	if(mid >= x)	change(p * 2, x, v);	//x在这个节点区间的左边，则往下判断左子树 
	else	change(p * 2 + 1, x, v);	//x在这个区间的右边，则往下啊判断右子树 
	t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);		//通过左右儿子对自己进行更新(前面已经排除没有子节点的情况) 
} 

int ask(int p, int l, int r)	//节点，待查询的左区间，右区间 
{
	if(l <= t[p].l && t[p].r <= r)		return t[p].dat;			//如果查询的区间包含节点的区间，直接返回节点的区间 
	int mid = t[p].l + t[p].r >> 1;					//节点区间的中点 
	int val = -(1 << 30);						//定义负无穷，不会对取最大值造成影响 
	if(mid >= l)	val = max(val, ask(p * 2, l, r));		//如果节点区间中值大于待查询的左边(包含)(空间思考)，搜左子树，进行分治dfs往下搜判断 
	if(r > mid)		val = max(val, ask(p * 2 + 1, l ,r));		// 如果待查询区间在节点区间中点右边(不包含)，搜右子树，进行dfs分治往下搜判断 
	return val; 		//返回值， 这个节点对整个区间的贡献 
}
int main()
{	
	build(1, 1, N);		//第一个节点，1 —N范围 
	change(1, 5, 9);	//第一个节点，把第五个改为 9 
	ask(1, 2, 9);		//第一个节点，查询2 —9的最值
	return 0;
}

延迟标记

线段树区间查询_spread函数的使用 —add标记
支持操作: 区间修改，区间查询和 

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct SegmentTree{
	ll sum, add;	//sum为和，add为懒惰标记
			//	1.（查询时没有完全覆盖的情况) 即先将值更新左右节点，然后下放用spread()下放add标记，保证递归调用的情况
			//	2. 查询时完全覆盖，直接返回当前区间的值（与单点更新版本类似) ,修改时则直接整个区间的sum加上长度 * 修改值d 
	int l, r;
}t[N << 2];		//4倍空间，单点更新中已证明 

int a[N], n, m;
void build(int p, int l, int r)		
{
	t[p].l = l, t[p].r = r;
	if(l == r)	{	t[p].sum = a[l]; return ;	}		//更新到单个点直接对应赋值 
	int mid = l + r >> 1;
	build(p << 1, l , mid);				//建左子树区间 
	build(p << 1 | 1, mid + 1, r);		//建右子树区间 
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;		//注意这里是 = 不是 += 
}

void spread(int p)		//传递标记的函数 
{
	if(t[p].add)	//如果有标记 
	{	//因为最后求得sum是由左右两个区间共同组成，所以先下传add标记(节点所代表的区间完全被覆盖除外, 此时不需要使用左右子树，但是要记录add标记，以后方便使用) 
		t[p << 1].sum += (ll)t[p].add * (t[p << 1].r - t[p << 1].l + 1);		//左子树(区间)值更新 
		t[p << 1 | 1].sum += (ll)t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);	//右子树(区间)值更新 
		t[p << 1].add += t[p].add;			//标记传给左子树 
		t[p << 1 | 1].add += t[p].add;		//标记传给右子树 
		t[p].add = 0; 			//下传标记结束，父亲节点的标记清除 
	}
}

void change(int p, int l, int r, int d)			//d为待改变的数值 
{
	if(l <= t[p].l && t[p].r <= r)			//完全覆盖 
	{
		t[p].sum += (ll)d * (t[p].r - t[p].l + 1);			//直接整个区间(左端点 - 右端点 + 1)更新 
		t[p].add += d;			//进行标记，便于访问子节点使用 
		return ;
	}
	spread(p);		//由于要访问子节点 
	int mid = t[p].r + t[p].l >> 1;				//取节点区间的左右节点 
	if(mid >= l)	change(p << 1, l, r , d);		//子节点中间 >= 查询区间左端点，去左子节点里去访问存在的区间 
	if(mid <  r)	change(p << 1 | 1, l ,r , d);	//子节点中间 < 查询区间右端点, 去右子节点里访问存在的区间 
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;				//节点和由左右子节点和更新 
}

ll ask(int p, int l, int r)
{
	if(l <= t[p].l && t[p].r <= r)	return t[p].sum;		//如果全部包含，直接返回值(不需要下传标记) 
	spread(p);							//没有完全覆盖，需要在左右子节点查询 
	int mid = t[p].l + t[p].r >> 1;
	ll val = 0;
	if(mid >= l)	val += ask(p << 1, l, r);		//同上，左右子节点里查询 
	if(mid < r)		val += ask(p << 1 | 1, l, r);
	return val;
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)	scanf("%d", &a[i]);
	build(1, 1, n); 		//建树，下标从1开始，方便对应 p << 1 和 p << 1 | 1 的左子节点和右子节点 
	while(m --)
	{
		int l, r, d;
		char op[2];			//输入格式, 用字符串类型 
		scanf("%s%d%d", op, &l, &r);
		if(op[0] == 'C')
		{
			scanf("%d", &d);
			change(1, l, r, d);			//区间改值 
		} 
		else printf("%lld\n", ask(1, l, r));	//询问区间和 
	}
	return 0;
}
0%