【每日一题Day277】LC2569更新数组后处理求和查询 | 线段树

**每日一题 Day277**

**LC2569 更新数组后处理求和查询**

在 LC2569 中，我们需要实现一个支持以下操作的数据结构：

* `add(i, val)`: 将值 `val` 添加到下标为 `i` 的元素中。
* `sumRange(i, j)`：返回从下标 `i` 到 `j` (含 `i` 和 `j`) 的元素之和。

我们将使用线段树来实现这个数据结构。线段树是一种用于解决区间问题的数据结构，特别适合于需要频繁更新和查询的场景。

### 线段树的基本概念线段树是一棵二叉树，每个节点代表一个区间。每个节点包含以下信息：

* `start`：区间的起始下标。
* `end`：区间的结束下标（含）。
* `sum`：区间内元素之和。

### 线段树的构建我们需要将原始数组转换为线段树。每个节点代表一个区间，包含以下信息：

class SegmentTreeNode:
 def __init__(self, start, end):
 self.start = start self.end = end self.sum =0

class SegmentTree:
 def __init__(self, nums):
 self.nums = nums self.root = self.build_tree(0, len(nums) -1)

 def build_tree(self, start, end):
 if start == end:
 node = SegmentTreeNode(start, end)
 node.sum = self.nums[start]
 return node mid = (start + end) //2 left_node = self.build_tree(start, mid)
 right_node = self.build_tree(mid +1, end)

 node = SegmentTreeNode(start, end)
 node.sum = left_node.sum + right_node.sum return node def add(self, i, val):
 self.update(self.root, i, val)

 def update(self, node, i, val):
 if node.start == node.end:
 node.sum += val return mid = (node.start + node.end) //2 if i <= mid:
 self.update(node.left, i, val)
 else:
 self.update(node.right, i, val)

 node.sum = node.left.sum + node.right.sum

def sum_range(self, i, j):
 return self.query(self.root, i, j)

def query(self, node, i, j):
 if node.start > j or node.end < i:
 return0 if node.start == node.end:
 return node.sum mid = (node.start + node.end) //2 sum_left = self.query(node.left, i, min(mid, j))
 sum_right = self.query(node.right, max(i, mid +1), j)
 return sum_left + sum_right

nums = [1,3,5,7,9]
segment_tree = SegmentTree(nums)

print(segment_tree.sum_range(0,2)) # Output:9 (1 +3 +5)
segment_tree.add(4,10)
print(segment_tree.sum_range(0,4)) # Output:35 (1 +3 +5 +7 +19)