如何用Python构建线段树？求助排查代码索引越界错误

咱们来一步步拆解你遇到的问题，以及对应的修复方案：

1. 核心问题：线段树存储空间不够 #

线段树的节点数量在最坏场景下需要4倍于原数组的长度（这是业内通用的安全经验值，能覆盖所有数组长度的情况）。你的原数组arr有6个元素，但你初始化的tree只有12个元素——当递归构建到深层节点时，节点编号（比如2*tn）会超出tree的最大索引，直接触发赋值越界错误。

举个例子：当递归到tn=8时，它的左子节点编号是2*8=16，但你的tree长度只有12，最大索引是11，这时候执行tree[16] = ...自然就会报错。

2. 次要问题：除法返回浮点数破坏递归逻辑 #

在Python3里，/运算符会返回浮点数，比如(0+5)/2得到的是2.5而非整数2。这会让递归过程中的start、mid、end变成浮点数类型，不仅可能引发后续的边界比较异常，还会间接导致节点编号计算出现混乱，进一步加剧索引越界的风险。

修复后的完整代码 #

下面是修正后的可运行代码：

def build(arr, start, end, tree, tn): 
    if end == start: 
        tree[tn] = arr[start] 
        return 
    # 用整数除法//得到整数类型的mid
    mid = (start + end) // 2 
    build(arr, start, mid, tree, 2 * tn) 
    build(arr, mid + 1, end, tree, 2 * tn + 1) 
    tree[tn] = tree[2 * tn] + tree[2 * tn + 1] 

arr = [1,2,3,4,5,6] 
# 初始化4倍原数组长度的线段树空间
tree = [0] * (4 * len(arr)) 
build(arr, 0, len(arr)-1, tree, 1) 
for i in tree: 
    print(i)

额外小贴士 #

• 你采用的根节点从1开始的写法是线段树的常见实现方式，这种情况下左子节点编号为2*tn、右子节点为2*tn+1，所以必须保证数组有足够的空间容纳这些节点。
• 直接用4*len(arr)初始化线段树空间是最省心的选择，不会浪费太多内存，同时能彻底避免索引越界的问题。

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