线段树

缘起

源于一道大厂的面试题

有一个日志文件，存放当天用户ID和上线，下线的时间（时间为从0 点开始到当前的秒数），这个日志文件有10亿条记录。请你设计一个算法，根据这个日志文件绘制当天在线人数曲线图。
日志文件内容如下：

1
2
3
4
5
6
UID       上线时间       下线时间
112       200            5000              

342       1320          20080   

………………总共有10亿条

分析

暴力设计此算法是简单的. 不就是要知道个时刻有多少用户在线上吗? 对于时刻 x，我们设在线人数为sum, sum的初始化值为0. 我们只需要遍历日志文件中的每一条数据，看看此人在此刻在不在线上. 如果在线上的话, 则sum++, 则遍历完日志文件之后, 求得sum, 就是x时刻在线人数. 我们就完成了曲线图的一个点的绘制工作. 但是

日志有10亿条！！！

你画一个点就要遍历10亿条，你怕是等到老板通知开除你你都画不完哦~ 囧

显然，我们需要更加高效的算法. 我们今日的主角线段树（SegmentTree）隆重登场.

其实上述问题等价于下面的问题

1
给定N=3条线段，{[2, 5], [4, 6], [0, 7]}, M=3个点{2, 4, 7},判断每个点分别在几条线段出现过

一条线段就是一条日志，一个点就是一个时刻。上面暴力算法的复杂度毫无疑问是 O(N*M), 所以必然超时. 这显然也不是大厂考察我们的目的.

线段树这种数据结构就可以处理这种问题. 唉，线段树的变式太多了. 这只是线段树能够处理的最典型问题。

线段树的算法是这样的, 首先，扫描N条线段，得到端点的最大值(max)和最小值(min)，这是O(N)内完成. 然后使用[min, max]按照递归算法建线段树(具体参见下面的算法实现，而且不难知道线段树是一棵平衡二叉树), 复杂度是O(max-min)（因为建树的操作无非就是建立了树中所有的节点呗，从而节点数量可以作为时间复杂度的度量，但是我们是知道叶子节点的个数的——恰好就是max-min+1个，即线段中单点的个数, 而因为线段树是一棵类似于但不是完全二叉树的树结构，见图1，所以我们完全可以根据叶子节点的个数估计树中节点的总数, 所以是O(max-min)）

​ 图1

得到线段树之后，就开始拿N条线段”插入”线段树，所谓插入其实也就是更改线段树中每个节点的cover属性（cover属性表示当前节点被插入的线段覆盖的次数）. 具体怎么更改，参见下面的具体算法.

最后要想知道每个点被几条线段覆盖过, 则只需要将此点”插入”线段树, 从根一直插到叶子. 一路上来将经过的各个节点的cover属性相加, 则最后得到的就是该点被多少条线段覆盖过了. 也就是此时刻在线人数.

先不谈实现，我们来看看这种算法下，之前大厂的面试题复杂度由 O(24*60*10^9)（假设仁慈一点，只要求绘出每分钟在线人数图， 则每分钟都要遍历10亿条）降低为多少?

首先是建树过程（这个过程称之为算法预热 Warm-Up）. 因为一天的时间是固定的, 就是1440分钟, 所以线段的范围是max=1440,min=0, 建树耗费 O(1440). 然后是插入线段树，因为线段树是平衡树，所以树高是O(log1440),，所以插入的复杂度是 O(log1440)10^9, 最后是询问, 复杂度是 O(1440\log1440)

所以最后的复杂度是O(1440+10^9log1440+1440\log1440)≈O(10.49*10^9)

即从1440个十亿变成了10个十亿, 算法效率提升了144倍. 这才是大厂真正想考察你的. 不多说，给出线段树实现模板

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
// panta.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
//#define LOCAL

using namespace std;

const int MAX_LEN = 10; // N条线段的跨度最大是10, 即N条线段的端点中的最大值-N条线段端点中的最小值<=10

struct
{
	int begin, end; // 此线段树上的节点表示线段是 [begin, end]
	int cover; // 表示此条线段被覆盖的次数

} segmenttree[MAX_LEN<<2]; // 线段树（数组实现比链表运行起来快）,索引0不用，则segmenttree[n]的左孩子是segmenttree[2*n],右孩子是 segmenttree[2*n+1]

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

void build(int begin, int end, int root) // 递归建树, 即使用 [begin, end]的线段建立线段树, 根节点是root
{
	if (begin > end) return; // 非法线段
	segmenttree[root].begin = begin; // 合法线段就要建立节点
	segmenttree[root].end = end;
	segmenttree[root].cover = 0;
	if (begin==end) return; // 如果是叶子节点——长度为1的单点， 则结束递归
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1); // 递归构建左子树
	build(mid+1, end, (root<<1)+1); //递归构建右子树
}

void insertordel(int begin, int end, int i, int flag) // 将[begin,end]这条线段"插入或者删除"线段树, 其实就是根据这条线段更改线段树中一些节点的cover属性, segmenttree[i]是当前线段树的节点 flag=0表示插入, flag=1表示删除
{
	if (segmenttree[i].begin==begin && segmenttree[i].end==end) // 如果当前节点所代表的线段刚好就是插入的线段的话
	{
		flag?segmenttree[i].cover--:segmenttree[i].cover++;
		return;
	}
	int mid = getmid(i); // 当前节点代表线段的中点
	if (mid>=end) insertordel(begin, end, i<<1, flag); // 如果[begin,end]完全包含在左子树中,则递归插入左子树
	else if (mid<begin) insertordel(begin, end, (i<<1)+1, flag); // 如果[beign, end] 完全包含在右子树中, 则递归插入右子树
	else // 如果 mid+1<=end&&begin<=mid, 则就要剖开 [begin,end]了
	{
		insertordel(begin, mid, i<<1, flag);
		insertordel(mid+1, end, (i<<1)+1, flag);
	}
}

int query(int x, int i) // 询问x被几条线段覆盖过? 返回被覆盖的次数, segmenttree[i]是当前线段树节点
{
	if (segmenttree[i].begin == segmenttree[i].end) return segmenttree[i].cover; // 如果是叶子节点
	return segmenttree[i].cover + (getmid(i)<x?query(x, (i<<1)+1):query(x, i<<1));
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int begin[3] = {2,4,0}, end[3]={5,6,7}, p[3] = {2,4,7};
	build(0, 7, 1); // 这里省略了求文章中的max和min的代码，这部分很简单，故略去
	for (int i = 0; i<3; i++) // 插入
	{
		insertordel(begin[i], end[i], 1, 0);
	}
	for (int i = 0; i<3;i++) // 询问
	{
		printf("%d\n", query(p[i], 1));
	}
	return 0;
}

至于为什么上面算法线段树的节点个数上限是(max-min)*4, 见上图1

max-min是3-1=2, 而需要准备7个节点（1的左右孩子虽然不存在，但是也要在数组上给他空着），所以 要准备2*4=8个位置.