课程中线段树的应用场景的具体解释

Question

Hi bobo老师，

我对9-1这节课7分25秒处提到的两个应用场景还不是很理解：

1. 2017年注册的用户中消费最高/最低/学习时间最长的用户？
2. 某个太空区域中的天体总量？

具体应该如何使用线段树对这两个问题建模呢？比如第一个问题里，如果用线段树建模的话，那么每个节点表示的是什么呢？是天？还是至今消费额？又如何能求出消费最高的用户是谁呢？

谢谢老师

Answer 1

liuyubobobo 2018-12-26 15:21:38

可能先看完这一章，对线段树有一个直观的了解以后，再来看这个问题，会更明确：）

在这一章，我们编程实现的线段树，我在main函数的调用里，传入了一个加法函数作为merger，所以可以使用线段树快速求出一个区间的和。只需要修改传入的merger函数是max，就可以很容易的利用线段树，快速求出一个区间的最大值（或者最小值，对应merger是min）。

再来看这里你提的两个应用：

对于第一个应用，是求2017年注册的用户中消费最高/最低/学习时间最长的用户？线段树中的每一个节点，表示一个时间段中的消费最高/最低/学习时间最长的用户。我们可以利用线段树，求解指定一个时间段中，消费最高/最低/学习时间最长的用户。本质就是利用线段树求解区间的最值；

第二个个应用，则是求一个二维区间中天体的数量。这个应用有点儿超纲，因为处理的是二维空间，需要使用线段树的拓展——二维线段树。这个课程中所介绍的线段树，本质是一维线段树。但这个应用本质，是求解一个区间的数量和（二维中的一个区域）。

总而言之，线段树是解决区间问题的利器（之一）：）

• 提问者 Poplar_hills #1

  明白了，非常感谢！