线段树写法的疑惑。
来源：1-4 线段树中的区间查询
数据结构呆瓜
2024-01-12 15:50:55
这个章节，就有点懵。
构建思路大概是懂的，以下是我的模糊理解。
先宏观上估计查询的时间复杂度：
通常的树，每个节点存放的是单个元素，或者说区间为1的信息。
线段树，每个节点存放的就是一段区间的信息。
我们查找任意区间的信息时，
对普通树，需把对应区间的元素位置全部找到，再提取；
对线段树，只需找到对应区间的位置，无需寻找区间内每个元素的位置，所以肯定快很多。
但问题是写法！！！！
其实线段树的创建我还勉强能跟得上，我感觉类似归并排序，它们都是在回归时候处理业务逻辑，有点二叉搜索后序遍历的感觉——先分解成最小区间，最后合并操作。
但线段树的查询我就很懵懂了，特别蒙蔽。让我写，一点思路都没有。
写回答
1回答
-
liuyubobobo
2024-01-12
对线段树的理解是 ok 的。
具体写法上，因为你没有提出一个具体的问题，所以我也无法回答，比如具体是代码的哪里不理解？你跟着课程代码写到哪里有疑惑了？觉得不懂了？
另外，从面试的角度，线段树完全可以不看，几乎不可能考察的。
继续加油！：）
0
相似问题