Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable （线段树Segment Tree）-超详细Python

题目

给定一个整数数组 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 = startself.end = endself.sum = 0self.left = Noneself.right = Noneclass NumArray:def __init__(self, nums: List[int]):def buildTree(nums, start, end):if start > end:return Noneif start == end:n = treeNode(start,end)n.sum = nums[start]return nmid = (start+end) // 2root = treeNode(start, end)root.left = buildTree(nums, start, mid)root.right = buildTree(nums, mid+1, end)root.sum = root.left.sum + root.right.sumreturn rootself.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 = valreturn valmid = (root.start+root.end) // 2if i <= mid:updateSum(root.left, i, val)else:updateSum(root.right, i, val)root.sum = root.left.sum + root.right.sumreturn root.sumupdateSum(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.summid = (root.start+root.end) // 2if 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个数之和。

复杂度

线段树：

• 创建树： $T = O(n)$
• 更新值： $T = O(logn)$
• 搜索Sum： $T = O(logn)$