线段树应用之线段覆盖总长度（另一种建树方式）

缘起

【1】中我们给出了线段树求解若干条线段覆盖区域总长度算法. 但是发现之前的建树方式有点麻烦——因为线段树分左右孩子的时候是没有端点重合的. 例如 [1,10]分割成[1,5]和[6,10]而漏掉了[5,6]区间. 但发现在处理着眼于线段、区间的问题中，这种建树方式是要做一些补救措施的——例如【1】中做的那样. 这是因为【1】中建树的方式着眼于”端点”， 【1】中建树的方式尽管不会漏掉任何一个端点，但是会漏掉一个区间, 我们把这种线段树成为点线段树. 点线段树对于处理只涉及端点的问题——例如【2】和【3】的时候很有效——或者说处理起来很优雅. 但是对于涉及线段啊，区间本身的时候，就显得力不从心、捉襟见肘了，例如【1】，所以我们针对【1】这种问题，再考虑另一种建树方式——区间线段树.

分析

点线段树在【3】中已经画过了，这里再画一次

而区间线段树长的样子是

可见，点线段树和区间线段树的区别有两点

  1. 点线段树左右孩子节点不会有端点重合，区间线段树恰有一个交界点重合
  2. 点线段树有单点区间作为叶子, 而区间线段树没有单点区间作为叶子, 区间线段树的叶子就是长度为1的区间. 这其实正应验了点线段树关注的是一个个的点，而区间线段树关注的是一段一段的区间.

那么回到【1】中的问题. 怎么使用区间线段树给出算法呢?

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
#include "stdafx.h"
#include<iostream>
#include <stdio.h>
#define LOCAL

using namespace std;

const int MAX_LEN = 20; // 线段最大跨度不超过20


struct
{
	int begin, end;
	int cover; // 被线段覆盖的次数
} segmenttree[MAX_LEN<<2];

inline int getmid(int i) {return (segmenttree[i].begin+segmenttree[i].end)>>1;}

void build(int begin, int end, int root)
{
	segmenttree[root].begin = begin;
	segmenttree[root].end = end;
	segmenttree[root].cover = 0;
	if (begin+1==end) return; // 区间线段树的叶子是一个个单位长度的区间
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1);
	build(mid, end, (root<<1)+1);// 左孩子是 [beign,mid] 右孩子是 [mid,end]
}

void insert(int begin,int end, int i)
{
	if (segmenttree[i].begin+1 == segmenttree[i].end) // 如果是叶子节点
	{
		segmenttree[i].cover++;
		return;
	}
	int mid = getmid(i);
	if (mid>=end) insert(begin, end, i<<1);
	else if (begin>=mid) insert(begin, end, (i<<1)+1);
	else  // begin<mid<end, 则线段[begin,end]被[begin,mid]和[mid,end]剖分
	{
		insert(begin, mid, i<<1);
		insert(mid, end, (i<<1)+1);
	}
}

int gettot(int i) // segmenttree[i]是线段树当前节点
{
	if (segmenttree[i].end==segmenttree[i].begin+1) return segmenttree[i].cover?1:0; // 如果已经是叶子了, 则返回叶子是否被覆盖, 如果覆盖了,则返回1, 否则返回0
	if (segmenttree[i].cover) return segmenttree[i].end-segmenttree[i].begin+1; //如果当前线段已经被覆盖了, 则直接返回线段长度
	return gettot(i<<1)+gettot((i<<1)+1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int begin[10] = {7 ,3, 8, 5, 6 ,11, 4 ,9 ,10, 2}, end[10]={8, 5 ,12, 6 ,9 ,15 ,7 ,10, 13, 3};
	build(2, 15, 1);
	for (int i = 0; i<10; i++)
	{
		insert(begin[i], end[i], 1);
	}
	printf("%d\n", gettot(1));
	return 0;
}
// 答案是13

是不是感觉比【1】整洁多了呢? 【1】中的点线段树和这里的区间线段树没有谁绝对的好与坏，关键看应用场景.

参考

【1】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%BA%94%E7%94%A8%E4%B9%8B%E7%BA%BF%E6%AE%B5%E8%A6%86%E7%9B%96%E6%80%BB%E9%95%BF%E5%BA%A6/

【2】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91-fzu-2171-%E9%98%B2%E5%AE%88%E9%98%B5%E5%9C%B0-II/

【3】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91/