Python栈的应用：线段树的实现

class SegmentTreeNode:
    def __init__(self, start, end, value = None):
        self.start = start
        self.end = end
        self.value = value
        self.left = None
        self.right = None
        if start < end:
            mid = (start + end) // 2
            self.left = SegmentTreeNode(start, mid)
            self.right = SegmentTreeNode(mid + 1, end)

class SegmentTree:
    def __init__(self, n):
        self.root = SegmentTreeNode(0, n - 1)

    def update(self, i, value):
        node = self.root
        stack = [node]
        while stack:
            node = stack.pop()
            if node.start == node.end:
                node.value = value
            else:
                mid = (node.start + node.end) // 2
                if i <= mid:
                    stack.append(node.left)
                else:
                    stack.append(node.right)
                stack.append(node)
        return self.root.value

    def query(self, start, end):
        node = self.root
        stack = [node]
        result = 0
        while stack:
            node = stack.pop()
            if node.start == start and node.end == end:
                result += node.value
            else:
                mid = (node.start + node.end) // 2
                if end <= mid:
                    stack.append(node.left)
                elif start > mid:
                    stack.append(node.right)
                else:
                    stack.append(node.right)
                    stack.append(node.left)
        return result

# 创建线段树
n = len("pidancode.com")
tree = SegmentTree(n)

# 更新某个位置的值
tree.update(5, 10)
tree.update(9, 15)

# 查询区间和
result = tree.query(3, 8)
print(result) # 输出：20