为何该迭代式线段树算法仅适用于完美二叉树？

问题背景 #

我参考实现了如下迭代式线段树构建算法，但该算法仅在数组长度为2的幂（完美二叉树场景）下有效，非完美二叉树场景会失效；而递归版本则可适配任意长度的数组。

迭代式实现代码 #

nums = [1,3,-2,8,-7]

N = len(nums)
tree = [0] * (N* 4)

def build_iterative():
    for i in range(N):
        tree[i + N] = nums[i]
    # 构建父节点
    for j in range(N - 1, 0, -1):
        tree[j] = tree[j * 2] + tree[j * 2 + 1]
build_iterative()

递归式实现代码 #

rtree = [0] * (4 * N)
def build_recursively(node, left, right):
    if left == right:
        rtree[node] = nums[left]
    else:
        mid = (left + right) // 2
        build_recursively(node * 2, left, mid)
        build_recursively(node * 2 + 1, mid + 1, right)
        rtree[node] = rtree[node * 2] + rtree[node * 2 + 1]

build_recursively(1, 0, N - 1)

迭代版仅支持完美二叉树的核心原因 #

• 叶子节点映射逻辑的局限性：迭代版直接将原数组元素放在tree[N ... N+N-1]的位置，这个逻辑的前提是线段树的叶子层刚好是从索引N开始的连续满层——只有当N是2的幂时，线段树的叶子节点会完全填满一层，每个叶子都对应原数组的有效元素。如果N不是2的幂（比如例子中的5），线段树的叶子层实际需要的是大于等于N的最小2的幂个节点（比如8），但迭代版只填充了前5个叶子，剩余3个叶子默认是0，计算父节点时会错误地把这些无效的0值纳入求和，导致结果偏差。
• 父节点计算的无差别遍历：迭代版从N-1倒序遍历到1，每个父节点j直接取2j和2j+1的和。但当N不是2的幂时，部分父节点的子节点并非都属于原数组的有效区间。比如N=5时，节点3对应原数组的区间[4,4]，它的子节点6和7中，7对应的是原数组不存在的索引5，迭代版会把tree[7]的0值加进去，导致节点3的值错误，进而上层所有依赖它的节点计算结果全部出错。

递归版适配任意长度的原因 #

递归版是基于区间划分逻辑构建的：

• 每次递归将当前区间拆分为左右两个子区间，直到区间长度为1（叶子节点），直接赋值原数组对应元素。
• 父节点的值仅合并有效子区间的结果，不管原数组长度是否为2的幂，递归都会精准处理有效区间内的节点，不会涉及无效的0值节点。比如N=5时，递归到节点3对应区间[4,4]，不会去处理不存在的子节点，直接赋值nums[4]，上层节点计算时只会合并有效子区间的结果，自然适配任意长度的数组。

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