课程中线段树的应用场景的具体解释
来源：9-1 什么是线段树
Poplar_hills
2018-12-26
Hi bobo老师，
我对9-1这节课7分25秒处提到的两个应用场景还不是很理解：
- 2017年注册的用户中消费最高/最低/学习时间最长的用户？
- 某个太空区域中的天体总量？
具体应该如何使用线段树对这两个问题建模呢？比如第一个问题里，如果用线段树建模的话，那么每个节点表示的是什么呢？是天？还是至今消费额？又如何能求出消费最高的用户是谁呢？
谢谢老师
写回答
1回答
-
可能先看完这一章，对线段树有一个直观的了解以后，再来看这个问题，会更明确：）
在这一章，我们编程实现的线段树，我在main函数的调用里，传入了一个加法函数作为merger，所以可以使用线段树快速求出一个区间的和。只需要修改传入的merger函数是max，就可以很容易的利用线段树，快速求出一个区间的最大值（或者最小值，对应merger是min）。
再来看这里你提的两个应用：
对于第一个应用，是求2017年注册的用户中消费最高/最低/学习时间最长的用户？线段树中的每一个节点，表示一个时间段中的消费最高/最低/学习时间最长的用户。我们可以利用线段树，求解指定一个时间段中，消费最高/最低/学习时间最长的用户。本质就是利用线段树求解区间的最值；
第二个个应用，则是求一个二维区间中天体的数量。这个应用有点儿超纲，因为处理的是二维空间，需要使用线段树的拓展——二维线段树。这个课程中所介绍的线段树，本质是一维线段树。但这个应用本质，是求解一个区间的数量和（二维中的一个区域）。
总而言之，线段树是解决区间问题的利器（之一）：）
012018-12-28
