### 题目描述 给你一个数组 nums ，请你完成两类查询。 1. 其中一类查询要求 更新 数组 nums 下标对应的值 2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right 实现 NumArray 类： - NumArray(int[] nums) 用整数数组 nums 初始化对象 - void update(int index, int val) 将 nums[index] 的值 更新 为 val - int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]） ### 输入输出 #### 示例1 ``` 输入： ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出： [null, 9, null, 8] 解释： NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1,2,5] numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8 ``` ### 题目解答 对于求解数组某个区间范围的元素和，通常采用累加的方式，通过两个位置数组和相减得到最终的结果。但如果要更改其中的一个数值，那么sum数组到数组尾部包含这个元素的都需要更改，这种方式会超时，需要进一步优化。 #### 思路 该问题采用分块处理的思路，将元素分成多个区间，这样的话，对于update操作，只需要对该区间进行更新即可，可以获得较快的更新速度。但是对于查询求和操作，需要对多个区间进行求和。 设数组num的大小为n，分成多个块，每个块的大小为size，那么一共划分了$$\lceil \frac{n}{size} \rceil$$个块，最后一个可能没有填满size。同时，我们需要用一个长度和块数量相同的数组，存储每个数组数字总和。 - 初始化操作： 对于初始化操作，我们需要将给的数组，计算块的数量，并且计算每个块的总和sum. - 更新操作 当更新某个块中的某个数字的时候，我们需要定位到这个块，根据这个位置之前存储的数字，加上相应的差值。 - 求和操作 求和操作需要根据我们给定的范围，看他俩是否在同一个块中，还是跨越多个块。根据不同情况进行分类讨论求和 **算法复杂度分析** 时间复杂度： 对于初始化，需要遍历整个数组，时间复杂度为$$O(N)$$ 对于更新，直接定位到该组，时间复杂度为$$O(1)$$ 对于计算，计算两端块求和的复杂度为$$O(size)$$，计算块级别求和的复杂度为$$O(\lceil \frac{n}{size} \rceil)$$, 整体时间复杂度为$$O(size + \lceil \frac{n}{size} \rceil)$$。为了使该部分的时间复杂度最小，可以求得使$$size=\sqrt{n}$$ #### 代码实现 ```python class NumArray: def __init__(self, nums: List[int]): self.size = int(len(nums) ** 0.5) self.nums = [[nums[self.size * j + i] for i in range(self.size)] for j in range(len(nums) // self.size)] self.nums.append(nums[- (len(nums) % self.size) :]) self.sums = [sum(li) for li in self.nums] def update(self, index: int, val: int) -> None: diff = val - self.nums[index // self.size][index % self.size] self.nums[index // self.size][index % self.size] = val self.sums[index // self.size] += diff def sumRange(self, left: int, right: int) -> int: left_i = left // self.size right_i = right // self.size if left_i == right_i: return sum(self.nums[left_i][left %self.size:right % self.size + 1]) else: left_sum = sum(self.nums[left_i][left % self.size:]) right_sum = sum(self.nums[right_i][:right % self.size+1]) mid_sum = 0 for i in range(left_i+1, right_i): mid_sum += self.sums[i] return left_sum + right_sum + mid_sum ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复