AcWing 1275. 最大数—线段树单点修改

**最大数—线段树单点修改**

### 题目描述给定一个长度为 n 的序列，要求实现一个线段树来支持以下操作：

* `update(i, x)`: 将第 i 个元素更新为 x。
* `query(l, r)`: 返回 [l, r] 范围内的最大值。

### 线段树结构我们使用一棵完全二叉树作为线段树，每个节点代表一个区间。每个节点包含以下信息：

* `max_val`: 当前区间内的最大值。
* `left` 和 `right`: 左子树和右子树对应的区间。

### 线段树操作#### 构造线段树

class SegmentTree:
 def __init__(self, nums):
 self.n = len(nums)
 self.tree = [[float('-inf'), i, i] for i in range(4 * self.n)]
 self.build_tree(nums,0,0, self.n -1)

 def build_tree(self, nums, node, start, end):
 if start == end:
 self.tree[node][0] = nums[start]
 return mid = (start + end) //2 self.build_tree(nums,2 * node +1, start, mid)
 self.build_tree(nums,2 * node +2, mid +1, end)
 self.tree[node][0] = max(self.tree[2 * node +1][0], self.tree[2 * node +2][0])

def update(self, i, x):
 self.update_tree(i, x,0,0, self.n -1)

def update_tree(self, i, x, node, start, end):
 if start == end:
 self.tree[node][0] = x return mid = (start + end) //2 if i <= mid:
 self.update_tree(i, x,2 * node +1, start, mid)
 else:
 self.update_tree(i, x,2 * node +2, mid +1, end)
 self.tree[node][0] = max(self.tree[2 * node +1][0], self.tree[2 * node +2][0])

def query(self, l, r):
 return self.query_tree(l, r,0,0, self.n -1)

def query_tree(self, l, r, node, start, end):
 if l > end or r < start:
 return float('-inf')
 if l <= start and r >= end:
 return self.tree[node][0]
 mid = (start + end) //2 left_max = self.query_tree(l, r,2 * node +1, start, mid)
 right_max = self.query_tree(l, r,2 * node +2, mid +1, end)
 return max(left_max, right_max)

nums = [3,5, -7,8,9]
tree = SegmentTree(nums)

print(tree.query(0,4)) # Output:9tree.update(2,10)
print(tree.query(1,4)) # Output:10