线段树

数据结构
字数统计: 2k   |   阅读时长≈ 9 分钟

基本介绍

1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。

2、每个节点以结构体的方式存储，结构体包含以下几个信息：

区间左端点、右端点；（这两者必有）

这个区间要维护的信息（事实际情况而定，数目不等）。

3、线段树的基本思想：二分。

4、线段树一般结构如图所示：

5、特殊性质：

由上图可得，

1、每个节点的左孩子区间范围为$[l,mid]$，右孩子为$[mid+1,r]$。

2、对于结点k，左孩子结点为$2\times k$，右孩子为$2\times k+1$，这符合完全二叉树的性质。

实现方式

要实现线段树，首先需要构造一颗树。

这里以结构体为例

1
2
3
4
5
6
struct {
	int l;//该节点的左边界
    int r;//该节点的右边界
    int sum;//该节点的值
    int lz;//之后说的lazytage
}tree[N<<2];//N为最大节点数量，需要开四倍大小。

1、建树

我们可以用递归的方式来建树。

给每个节点记录他的左边界和右边界。

然后递归左子树和右子树。

如果该节点左右边界相等，则说明是子节点，赋值后结束递归。

建树之后记得更新自身的值。

1
2
3
4
5
6
7
8
9
10
11
void build(int i=1,int l=1,int r=n) {
	tree[i].l = l, tree[i].r = r;
	if (l == r) {
		tree[i].sum = num[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid);//建左子树
	build(i << 1 | 1, mid + 1, r);//建右子树
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

2、区间修改

为了实现区间修改的功能，我们需要引入一个叫做“lazytage”的东西，就是懒标记。

正如他的名字所说，最大的特点就是懒，只有需要用到他的时候才需要他。

当需要他的时候，就需要一个操作，“pushdown”。

其实意思很好理解，就是将该节点的标记进行下传。

他的左子树和右子树加上该节点的懒标记，同时更新左右子树的值。

1
2
3
4
5
6
7
8
9
10
11
void pushdown(int i) {
	if (tree[i].lz != 0) {
		tree[i << 1].lz += tree[i].lz;//标记下传
		tree[i << 1 | 1].lz += tree[i].lz;
		int mid = (tree[i].l + tree[i].r) >> 1;
		tree[i << 1].sum += tree[i].lz * (mid - tree[i].l + 1);//标记乘上区间长度
		tree[i << 1 | 1].sum += tree[i].lz * (tree[i].r - mid);
		tree[i].lz = 0;
	}
	return;
}

在修改的时候，如果某一个节点的区间完全被包含在需要修改的区间中，我们只需要修改这个节点的值，也就是加上标记乘以区间长度的值，并且给他的标记数量加上$k$。

如果不是完全包含在其中的，也就意味我们需要继续的搜索，也意味着我们需要用到这个节点的子节点。

还记得懒标记的定义吗——“只有需要用到他的时候才需要他”。

所以我们需要将懒标记下传。

（这里很重要，我搞懂这里想了好久。。

如果不下传的话，就会导致查询到的值不真实。

如果左子树与这个区间有交集，就搜索左子树。

如果右子树与这个区间有交集，就搜索右子树。

1
2
3
4
5
6
7
8
9
10
11
void add(int i,int l,int r,int k) {
	if (tree[i].l >= l && tree[i].r <= r) {//如果完全被包含，就直接修改
		tree[i].sum += k * (tree[i].r - tree[i].l + 1LL);
		tree[i].lz += k;
		return;
	}
	pushdown(i);//下传标记
	if (tree[i << 1].r >= l)	add(i << 1, l, r, k);//搜索左子树
	if (tree[i << 1 | 1].l <= r)	add(i << 1 | 1, l, r, k);//搜索右子树
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

3、区间查询

从根节点开始搜索。

如果该节点的区域完全被包含在查询的区间中，返回该节点的值即可。

如果该节点的区域在查询的区间外，则直接返回0。

如果我们还需要向下搜索的话，同样是需要pushdown的。

原因同上，我们仍然需要使用到该节点的子节点。

接下来就是类似的了。

如果左子树与这个区间有交集，就搜索左子树。

如果右子树与这个区间有交集，就搜索右子树。

1
2
3
4
5
6
7
8
9
long long quiry(int i ,int l,int r) {
	long long ans = 0;
	if (tree[i].l >= l && tree[i].r <= r)	return tree[i].sum;//如果完全在其中，则直接返回值
	if (tree[i].r<l || tree[i].l>r)	return 0;//超出区间外，直接返回0
	pushdown(i);
	if (tree[i << 1].r >= l)	ans += quiry(i << 1, l, r);//加上左子树
	if (tree[i << 1 | 1].l <= r)	ans += quiry(i << 1 | 1, l, r);//加上右子树
	return ans;
}

（其实线段树还有很多内容，像基础的单点修改，区间查询，区间修改，单点查询，这些完全可以用区间修改和区间查询替代，所以就不讲了。

在区间修改中，懒标记不止有加法，还存在乘法和根号，这些不会。。

（以后可能会补。。大概

想要了解的话，可以点击这里。

因为自己了解的也不是很深，可能没有讲明白。。

不懂的话可以点击上面那个链接。

典型例题

1、洛谷P3372 【模板】线段树 1

题目大意

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

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

解题思路

典型的区间修改加区间查询。

线段树模板。

完整代码

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
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 5;
int num[N],n;
struct {
	long long sum, lz;
	int l, r;
}tree[N<<2];

void build(int i=1,int l=1,int r=n) {
	tree[i].l = l, tree[i].r = r;
	if (l == r) {
		tree[i].sum = num[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

void pushdown(int i) {
	if (tree[i].lz != 0) {
		tree[i << 1].lz += tree[i].lz;
		tree[i << 1 | 1].lz += tree[i].lz;
		int mid = (tree[i].l + tree[i].r) >> 1;
		tree[i << 1].sum += tree[i].lz * ((long long)mid - tree[i].l + 1);
		tree[i << 1 | 1].sum += tree[i].lz * (tree[i].r - (long long)mid);
		tree[i].lz = 0;
	}
	return;
}

void add(int i,int l,int r,int k) {
	if (tree[i].l >= l && tree[i].r <= r) {
		tree[i].sum += k * (tree[i].r - tree[i].l + 1LL);
		tree[i].lz += k;
		return;
	}
	pushdown(i);
	if (tree[i << 1].r >= l)	add(i << 1, l, r, k);
	if (tree[i << 1 | 1].l <= r)	add(i << 1 | 1, l, r, k);
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

long long quiry(int i ,int l,int r) {
	long long ans = 0;
	if (tree[i].l >= l && tree[i].r <= r)	return tree[i].sum;
	if (tree[i].r<l || tree[i].l>r)	return 0;
	pushdown(i);
	if (tree[i << 1].r >= l)	ans += quiry(i << 1, l, r);
	if (tree[i << 1 | 1].l <= r)	ans += quiry(i << 1 | 1, l, r);
	return ans;
}

int main() {
	int m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)	scanf("%d", &num[i]);
	build();
	for (int i = 1; i <= m; i++) {
		int g;
		cin >> g;
		if (g == 1) {
			int x,y, k;
			scanf("%d%d%d", &x, &y,&k);
			add(1, x, y, k);
		}
		else {
			int x, y;
			scanf("%d%d", &x, &y);
			cout << quiry(1, x, y) << endl;
		}
	}
}

2、CF-12D Ball

因为这道题我已经写过题解了，这里就不再赘述。

想要了解的可以去看我之前写的题解。

点击这里

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信