线段树built的非递归写法

线段树（Segment Tree），也称为区间树，是一种数据结构，常用于处理区间查询和更新的问题。非递归构建线段树通常采用迭代的方式，通过维护两个指针，一个指向当前节点的位置，另一个指向其子节点的位置，逐步构建整个树的过程。

以下是线段树非递归构建的一个基本步骤：

1. **初始化**：创建一个数组，长度是目标线段树的节点数，通常是原始数据范围的两倍。数组的第一个元素作为根节点，对应的是整个数据区间的值。

2. **分治过程**：对于每个索引 `i`，从最后一个非叶子节点开始遍历，将其子节点设置为原数组上 `i * 2 + 1` 和 `i * 2 + 2` 的值，然后将当前节点的值设为其左右子节点值的相应操作（如求和、最大值等）。这里的关键是每次迭代都把索引移动到对应的子区间。

3. **结束条件**：当`i`变为0时停止，因为此时`i`已经到达了最底层，即所有的叶子节点都已经设置了正确的值。

非递归写法可以保证代码清晰易懂，避免了函数调用带来的额外开销。以下是伪代码示例：

def build_segment_tree(arr):
    n = len(arr)
    tree = [None] * (2 * n)  # 创建空的线段树数组
    for i in range(n - 1, -1, -1):  # 从最后一个元素开始
        tree[i] = arr[i]  # 初始化叶子节点
        if i * 2 + 1 < len(tree):
            tree[i] = combine(tree[i], tree[i * 2 + 1])  # 结合左子节点
        if i * 2 + 2 < len(tree):
            tree[i] = combine(tree[i], tree[i * 2 + 2])  # 结合右子节点

    return tree

其中`combine`函数是针对具体应用场景确定的操作，比如求和操作就是对两个值直接相加。