1回答

liuyubobobo

2022-11-15

我不确定你想要的微观解释具体是指什么。课程中介绍链表的时候所说的微观解释，是指对递归运行过程的理解。如果你学到了这里，对链表的递归算法，BST 的递归算法，包括快速排序，归并排序等算法的递归过程的理解都没有问题，那么你就已经理解了递归的运行过程了。（如果你觉得你对递归过程的理解还不够透彻，你不应该改线段树。最好的练习是基于普通的树结构上的递归算法做理解，辅以一定量的力扣上的 Tree 标签的问题。）

如果你已经明白了递归是如何运行的，那么对于线段树来说，最难理解的关键在于：线段树上的递归算法涉及的参数是更多的，这可能会让你觉得更混乱。（实际上创建过程相比后续的查询过程而已，还是简单的。）

我的建议是：

1）首先，接受：线段树本身就是更难理解这个事实。它本身就是比链表或者 BST 更难啃的骨头。

2）把对线段树的理解过程看做一个练习。实际这是一个很好的练习，来帮助你学习如何自己具体的跟踪一个算法的运行过程。

3）请你首先不要想程序的具体实现是什么，理解线段树上的每个节点具体是存什么的。具体而言，就是理解这页 ppt。我建议你使用一个具体的用例，比如 8 个数据 [1, 2, 3, 4, 5, 6, 7, 8]，merger 操作是求和，把这页 ppt 上线段树上每个节点上都存的是多少，自己用纸笔上理清楚：

4）如果能用纸笔把这个结构画出来，现在，在程序中，去具体的跟踪程序的运行过程。以 buildSegmentTree 为例，跟踪的过程包括：

    a. 每次递归执行的参数都是什么？为什么? (buildSegmentTree 只有三个参数，treeIndex, l 和 r，他们是如何对应的？)

   b. 每次递归的过程的逻辑是什么？在做什么事情？为什么这么做？

   c. 每次其实递归最终都是为了算出 tree[treeIndex]，每次递归算出来的结果是什么？这组参数为什么算出来的是这个结果？算出来的这个结果和你使用纸笔绘制的线段树上的数据是怎样对应的？

这样的一个用例只有 15 个节点，其中还有 8 个叶子节点根本不需要计算，只需要计算 7 个节点的值。我建议你踏踏实实拿出一下午的时间，仿照我在归并排序中跟踪算法执行过程的方式，跟踪这个程序的运行。看一看整个过程到底是如何执行的？为什么这么执行？最终是如何得到我们想要的结果的？

=========

说实话，从面试的角度看，线段树并不重要，考察的概率极低。（如果你没有耐心做上面的事情，忘记线段树，对于 90% 的面试，尤其是国内的面试，是不会有影响的。）

但是，这样实际地去通过调试，跟踪，更加具体的理解递归（或者一段逻辑的执行过程），是非常非常重要的。我们学习算法，主要学的其实不是一个又一个的结构和算法，想要排序，语言库里有 sort，想要红黑树哈希表，语言库里有 TreeSet, HashMap。那我们为什么还要学习它们的底层原理？

因为我们是在通过具体地学习一个又一个的结构或者算法，更深刻地理解计算机解决问题的方式和思想，理解诸如递归这样的逻辑构成方式。当我们面对新的问题的时候，能够把这样类似的方式使用上。这个时间省不得。只有通过这个过程，你才能真的进步，才能真的觉得“学到了”。

如果你在以上模拟跟踪的过程中，遇到了更具体的问题，比如对于什么数据，走到了某一步，你认为程序应该如何执行，或者程序计算的结果应该是怎样的，但实际又是怎样的，和你的想法矛盾了，你不理解了，你可以再把这个具体的问题摆上来，我们再来讨论。

继续加油！：）

0