【Leetcode】每日一题：区域和检索 - 数组可修改

区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。 其中一类查询要求 更新 数组 nums 下标对应的值 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left None: self.sumarray[index // self.size] += val - self.nums[index] self.nums[index] = val def sumRange(self, left: int, right: int) -> int: if left // self.size == right // self.size: return sum(self.nums[left : right + 1]) else: m = self.size b1, b2 = left // m, right // m return sum(self.nums[left: (b1+1) * m]) + sum(self.sumarray[b1 + 1 : b2]) + sum(self.nums[(b2 * m) : right + 1]) 官方代码

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.n = n
        self.seg = [0] * (n * 4)
        self.build(nums, 0, 0, n - 1)

    def build(self, nums: List[int], node: int, s: int, e: int):
        if s == e:
            self.seg[node] = nums[s]
            return
        m = s + (e - s) // 2
        self.build(nums, node * 2 + 1, s, m)
        self.build(nums, node * 2 + 2, m + 1, e)
        self.seg[node] = self.seg[node * 2 + 1] + self.seg[node * 2 + 2]

    def change(self, index: int, val: int, node: int, s: int, e: int):
        if s == e:
            self.seg[node] = val
            return
        m = s + (e - s) // 2
        if index  int:
        if left == s and right == e:
            return self.seg[node]
        m = s + (e - s) // 2
        if right  m:
            return self.range(left, right, node * 2 + 2, m + 1, e)
        return self.range(left, m, node * 2 + 1, s, m) + self.range(m + 1, right, node * 2 + 2, m + 1, e)

    def update(self, index: int, val: int) -> None:
        self.change(index, val, 0, 0, self.n - 1)

    def sumRange(self, left: int, right: int) -> int:
        return self.range(left, right, 0, 0, self.n - 1)

# 作者：LeetCode-Solution

1、选择分块的思想很自然，但是具体计算出根号能够达到时间空间最优这个思路确实很棒 2、接触到了线段树的概念，python做树的题需要思考一下引用和指针的区别，不然这种涉及到递归的问题容易混乱