python线段树实现查找区间内最大的值

下面是使用 Python 实现线段树查找区间内最大值的代码：

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n * 4)
        self.build_tree(nums, 0, 0, self.n - 1)
    
    def build_tree(self, nums, i, l, r):
        if l == r:
            self.tree[i] = nums[l]
        else:
            mid = (l + r) // 2
            self.build_tree(nums, i * 2 + 1, l, mid)
            self.build_tree(nums, i * 2 + 2, mid + 1, r)
            self.tree[i] = max(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    
    def query(self, i, l, r, ql, qr):
        if ql <= l and qr >= r:
            return self.tree[i]
        elif ql > r or qr < l:
            return float('-inf')
        else:
            mid = (l + r) // 2
            left = self.query(i * 2 + 1, l, mid, ql, qr)
            right = self.query(i * 2 + 2, mid + 1, r, ql, qr)
            return max(left, right)

其中，SegmentTree 类的构造函数中，build_tree 方法用于构建线段树；query 方法用于查询区间内的最大值。具体实现如下：

1. build_tree 方法中，i 是当前节点的下标，l 和 r 分别是当前节点所代表的区间的左端点和右端点。如果区间只有一个元素，则将当前节点的值设为该元素的值；否则，递归构建左右子树，并将当前节点的值设为左右子树中的最大值。
2. query 方法中，i、l 和 r 的含义同上，ql 和 qr 分别是查询区间的左端点和右端点。如果当前节点所代表的区间完全包含在查询区间内，则返回当前节点的值；如果当前节点所代表的区间完全不在查询区间内，则返回负无穷；否则，递归查询左右子树，并返回左右子树中的最大值。

使用示例：

nums = [1, 3, 2, 7, 9, 11]
st = SegmentTree(nums)
print(st.query(0, 0, st.n - 1, 1, 4))  # 输出：7

其中，nums 是待构建线段树的列表，st 是构建的线段树对象，st.query(0, 0, st.n - 1, 1, 4) 表示查询 nums[1:5] 区间内的最大值，结果为 7。