307. 区域和检索 – 数组可修改

题目描述 给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。 update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。 示例: Given nums = [1, 3, 5] sumRange(0, 2) -> 9update(1, 2)sumRange(0, 2) -> 8说明: 数组仅可以在 update 函数下进行修改。 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/range-sum-query-mutable著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Prefix sum 我们可以预先计算出前缀和存储在数组中,prefix[i] = num[0]+…+nums[i]。这样,当需要求得范围[i,j]的和时,我们可以通过prefix[j]-prefix[i-1]在O(1)的时间计算出结果。但是当nums[i]发生更新操作,那么我们不得不重新计算prefix[i]之后的前缀和,时间复杂度为O(n)。 全部代码如下: 解法2 – Fenwick Tree(树状数组) Fenwick Tree也称为树状数组,它可以在O(logn)的时间得到任意前缀和,并同时支持在O(logn)时间内支持动态单点值的修改。空间复杂度O(n)。为了实现Fenwick Tree,我们需要一个函数lowbit(x),他是用来求得数值x最低位第一个1所代表到数值,例如x = 0110,lowbit(x) = 0010; x = 0101, lowbit(x) = 0001。…

Read more