Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable (线段树Segment Tree)-超详细Python
程序员文章站
2022-07-13 11:03:31
...
题目
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。
链接:https://leetcode.com/problems/range-sum-query-mutable/
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Constraints:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
- 0 <= i <= j <= nums.length - 1
Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
思路及代码
线段树 Segment Tree
- 线段树定义:如图,每个叶子结点代表数组中的每个值,每个结点的start和end两个属性代表数组中的index,值则是该段index的和。
- 创建树
- 更新数组中某一元素的值:类似二分查找index,最后找到叶子结点,更新叶子的值,及所有父结点的值
- 搜索区间和:分别找两个端点落在的左/右子树,比如找0-3就是找到0-2+3-3
class treeNode:
def __init__(self, start, end):
self.start = start
self.end = end
self.sum = 0
self.left = None
self.right = None
class NumArray:
def __init__(self, nums: List[int]):
def buildTree(nums, start, end):
if start > end:
return None
if start == end:
n = treeNode(start,end)
n.sum = nums[start]
return n
mid = (start+end) // 2
root = treeNode(start, end)
root.left = buildTree(nums, start, mid)
root.right = buildTree(nums, mid+1, end)
root.sum = root.left.sum + root.right.sum
return root
self.root = buildTree(nums, 0, len(nums)-1)
def update(self, i: int, val: int) -> None:
def updateSum(root, i, val):
if root.start == root.end:
root.sum = val
return val
mid = (root.start+root.end) // 2
if i <= mid:
updateSum(root.left, i, val)
else:
updateSum(root.right, i, val)
root.sum = root.left.sum + root.right.sum
return root.sum
updateSum(self.root, i, val)
def sumRange(self, i: int, j: int) -> int:
def sumR(root, i, j):
if root.start == i and root.end == j:
return root.sum
mid = (root.start+root.end) // 2
if j <= mid:
return sumR(root.left, i, j)
if i > mid:
return sumR(root.right, i, j)
return sumR(root.left, i, mid) + sumR(root.right, mid+1, j)
return sumR(self.root, i, j)
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)
树状数组 Binary Indexed Tree / Fenwick Tree
- 用于解决的问题:
- 更新某一index的值:O(n)
- 求位置i到位置j的数字和:O(1)
- 构造:根据数字的二进制表示来对数组中的元素进行逻辑上的分层存储
- 每个节点的父结点是自己加上二进制最右的1:i += lowbit(i)。lowbit(x) = x & (-x)
- 比如3=0011,父结点为0011+0001=0110,即4;4=0110,父结点0110+0010=1000,即8。
- 求区间和:
- i -= lowbit(i)
- 比如求前7个数之和:7=0111,上一个是0110,再上一个是0100,把这三个结点加和就是前7个数之和。
复杂度
线段树:
- 创建树:
- 更新值:
- 搜索Sum: