构建存Min/Max的Segment Tree时子节点类型不一致报错的解决方法

嘿，这个问题我之前也碰到过——你的线段树里叶子节点存的是整数，非叶子节点存的是[min, max]列表，类型不统一，调用min/max函数时自然会报错（毕竟整数和列表没法直接比较大小嘛）。

问题根源拆解 #

看你的代码逻辑：

• 叶子节点（low==high时）：直接把arr[low]（整数）赋值给segment_tree[pos]
• 非叶子节点：把[min(子节点), max(子节点)]（列表）赋值给segment_tree[pos]

当递归到上层节点计算时，子节点可能一个是整数、一个是列表，min()函数收到混合类型的参数，直接触发类型错误。

解决方案：统一所有节点的数据结构 #

不管是叶子节点还是非叶子节点，都存储[min_value, max_value]格式的列表。这样所有节点结构一致，计算父节点时就能正确提取子节点的min和max值。

修改后的完整代码如下：

from math import log2, ceil

def segment(low, high, pos):
    if low == high:
        # 叶子节点的min和max都是自身的值，统一存为列表
        segment_tree[pos] = [arr[low], arr[low]]
        return
    mid = (high + low) // 2
    segment(low, mid, 2*pos+1)
    segment(mid+1, high, 2*pos+2)
    # 现在子节点都是[min, max]列表，分别取它们的min和max计算父节点
    left_child = segment_tree[2*pos+1]
    right_child = segment_tree[2*pos+2]
    segment_tree[pos] = [
        min(left_child[0], right_child[0]),
        max(left_child[1], right_child[1])
    ]

length = 5
arr = [1,2,3,4,5]
low = 0
high = length - 1
height = int(ceil(log2(length)))
pos = 0
size_of_segment_tree = 2*int(pow(2, height)) - 1
segment_tree = [0]*size_of_segment_tree
segment(low, high, pos)

# 可以打印验证结果
print(segment_tree)

修改后的效果 #

运行这段代码后，线段树的所有节点都是[min, max]格式：

• 叶子节点：比如对应arr[0]=1的节点是[1,1]，对应arr[4]=5的节点是[5,5]
• 上层节点：比如根节点会是[1,5]（整个数组的min和max），覆盖[1,2,3]的中间节点是[1,3]

这样后续不管是查询区间min还是max，都能通过统一的节点结构快速提取对应值，再也不会出现类型错误啦。

内容的提问来源于stack exchange，提问作者Om Sharma