LeetCode 区间修改区间查询题解

LeetCode 区间修改区间查询题解题目描述实现一个数据结构支持以下操作区间增加给某个区间的所有元素增加一个值区间查询返回某个区间的元素和解题思路方法线段树懒惰传播思路使用线段树和懒惰传播。每个节点维护一个懒标记表示需要增加的量。查询和更新时将懒标记向下传递。复杂度分析时间复杂度O(log n)。空间复杂度O(n)。代码实现class SegmentTree: def __init__(self, nums): self.n len(nums) self.tree [0] * (4 * self.n) self.lazy [0] * (4 * self.n) self.build(1, 0, self.n - 1, nums) def build(self, node, l, r, nums): if l r: self.tree[node] nums[l] else: mid (l r) // 2 self.build(node * 2, l, mid, nums) self.build(node * 2 1, mid 1, r, nums) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def push_down(self, node, l, r): if self.lazy[node] ! 0: mid (l r) // 2 self.tree[node * 2] self.lazy[node] * (mid - l 1) self.tree[node * 2 1] self.lazy[node] * (r - mid) self.lazy[node * 2] self.lazy[node] self.lazy[node * 2 1] self.lazy[node] self.lazy[node] 0 def update(self, node, l, r, ql, qr, val): if ql r or qr l: return if ql l and r qr: self.tree[node] val * (r - l 1) self.lazy[node] val return self.push_down(node, l, r) mid (l r) // 2 self.update(node * 2, l, mid, ql, qr, val) self.update(node * 2 1, mid 1, r, ql, qr, val) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def query(self, node, l, r, ql, qr): if ql r or qr l: return 0 if ql l and r qr: return self.tree[node] self.push_down(node, l, r) mid (l r) // 2 return self.query(node * 2, l, mid, ql, qr) self.query(node * 2 1, mid 1, r, ql, qr) # 测试 def test_segment_tree(): nums [1, 2, 3, 4, 5] st SegmentTree(nums) print(st.query(1, 0, 4, 0, 2)) # 输出6 st.update(1, 0, 4, 0, 2, 1) print(st.query(1, 0, 4, 0, 2)) # 输出9 if __name__ __main__: test_segment_tree()总结线段树可以高效地实现区间修改和区间查询操作通过懒惰传播优化性能。