欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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的和。

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

  • 创建树
  • 更新数组中某一元素的值:类似二分查找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个数之和。

复杂度

线段树:

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