一、先从“二分查找”说起假设你有一本按页码编号的电话簿从第1页到第100页。你想找第37页上的人名。普通查找从第1页开始翻一页一页往后翻翻到第37页。最坏情况要翻100次。二分查找先翻到中间第50页。37 50所以目标在前半本。再翻到前半本的中间第25页。37 25所以在后半本25~50之间。再翻到25~50的中间第37页。找到了。只翻了3次。这就是二分——每次把搜索范围砍掉一半。二、从“二分查找”到“树”现在问题变了你不再只是找某一页而是要频繁地查任意连续几页里人名拼音最靠后的是谁相当于最大值。比如问你“第30页到第50页之间人名拼音最靠后的是谁”如果你每次都从第30页翻到第50页一页一页比过去那就太慢了。能不能像二分查找那样提前把一些“汇总信息”存好查的时候直接拿这就是“树”要做的事情。三、画一棵“汇总树”假设我们有8个时间戳1, 2, 3, 4, 5, 6, 7, 8。每个时间戳上有一个数值。我们先把它们两两分组每组选出一个最大值第1层原始数据 时间戳: 1 2 3 4 5 6 7 8 数值: 10 5 8 3 12 7 9 4 第2层两两一组取最大值 (1,2) → max(10,5) 10 (3,4) → max(8,3) 8 (5,6) → max(12,7) 12 (7,8) → max(9,4) 9 第3层再两两一组取最大值 (1~4) → max(10,8) 10 (5~8) → max(12,9) 12 第4层最终 (1~8) → max(10,12) 12把这个过程画成树的样子(1~8): 12 / \ (1~4): 10 (5~8): 12 / \ / \ (1~2): 10 (3~4): 8 (5~6): 12 (7~8): 9 / \ / \ / \ / \ 1:10 2:5 3:8 4:3 5:12 6:7 7:9 8:4这棵树就是线段树。最下面一排是原始数据叶子节点。上面每一层都是下一层的“汇总”——两个子节点的最大值。最上面是整棵树的“总最大值”。四、用这棵树来查询现在问你“时间戳3到时间戳6之间的最大值是多少”不用一个一个看。我们从树顶往下走根节点 (1~8)太大了不完全在3~6内所以往下走。左孩子 (1~4)部分重叠3~4在范围内继续往下。右孩子 (5~8)部分重叠5~6在范围内继续往下。(1~4) 的左孩子 (1~2)完全不重叠1~2不在3~6内跳过。(1~4) 的右孩子 (3~4)完全在3~6内直接拿它的值 8。(5~8) 的左孩子 (5~6)完全在3~6内直接拿它的值 12。(5~8) 的右孩子 (7~8)完全不重叠跳过。结果max(8, 12) 12。我们只看了几个节点就得到了答案不需要遍历所有8个时间戳。五、为什么叫“动态开点”刚才的例子中我们把所有8个时间戳都画出来了。但实际题目中时间戳范围是1到10^9你不可能真的把这10亿个节点都建好——内存不够。动态开点的意思是只有当你真正用到某个时间戳时才创建它对应的节点。比如你只收到了时间戳1、5、10的数据那树就只长成这样(1~10^9) / \ (1~5 * 10^8) (5 * 10^81 ~ 10^9) / \ (1~2.5 * 10^8) (2.5 * 10^81 ~ 5 * 10^8) / \ (1~1) (2~2.5 * 10^8) | 1:10实际上树只会沿着你用到的路径生长。没用到的区间节点根本就不存在None。这就叫“动态开点”——用多少长多少。六、总结线段树到底干了什么你的问题线段树的回答我要在时间戳5上存一个值从树顶往下走找到时间戳5的叶子存进去。然后一路回溯更新沿途所有父节点的最大值。我要查时间戳3~6的最大值从树顶往下走碰到完全在3~6内的节点就直接拿值碰到完全不在的就跳过部分重叠的就继续往下。最后把所有拿到的值取最大。时间戳范围太大动态开点只用到的节点才创建不浪费内存。整个过程就是“二分思想”的延伸把一个大区间不断对半拆分每个小区间都提前算好“汇总值”。查询时通过二分快速定位到需要的小区间直接拿汇总值不用一个一个数。七、一个让你彻底理解的类比想象你是一个班主任手下有1000个学生学号从1到1000。你想随时知道任意连续学号段里最高分是多少。笨办法每次有人问你就把那个学号段的所有学生成绩翻一遍。1000个学生问1000次就是100万次操作。线段树办法你提前把所有学生按学号分组1~1000 为一组记下最高分分成两组1~500 和 501~1000分别记下最高分再分1~250、251~500、501~750、751~1000分别记下最高分……直到每个学生单独一组现在有人问“学号237到学号684的最高分是多少”你只需要看237~684覆盖了哪些“提前分好组”的区间把这些区间的最高分拿出来比一比得出答案你不需要看每一个学生的成绩只需要看几个“小组汇总”就够了。这就是线段树。