网站建设项目立项登记 表,网页设计实验报告模板,搜索引擎推广方法,做好一个网站需要多久1. 题目
给定一个整数数组 nums#xff0c;求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和#xff0c;包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val#xff0c;从而对数列进行修改。
示例:
Given nums [1, 3, 5]
sumRange(0, 2) - …1. 题目
给定一个整数数组 nums求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val从而对数列进行修改。
示例:
Given nums [1, 3, 5]
sumRange(0, 2) - 9
update(1, 2)
sumRange(0, 2) - 8说明:
数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。来源力扣LeetCode 链接https://leetcode-cn.com/problems/range-sum-query-mutable 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 303. 区域和检索 - 数组不可变前缀和
2.1 常规前缀和
class NumArray {int *sum NULL;int n;
public:NumArray(vectorint nums) {if(nums.empty())return;n nums.size();sum new int [n];sum[0] nums[0];for(int i 1; i nums.size(); i)sum[i] sum[i-1]nums[i];}void update(int i, int val) {if(!sum)return;int differ;if(i 0)differ val-sum[i];elsediffer val-(sum[i]-sum[i-1]);for(int k i; k n; k)sum[k] differ;}int sumRange(int i, int j) {if(!sum)return 0;if(i ! 0)return sum[j]-sum[i-1];return sum[j];}
};236 ms 18.9 MB
2.2 树状数组
参考树状数组介绍降低更新复杂度为 logn\log nlogn
class NumArray {vectorint v;vectorint copy;int N;
public:NumArray(vectorint nums) {N nums.size();v.resize(N1,0);//树状数组要求下标从1开始copy.resize(N1,0);for(int i 0; i N; i)update(i,nums[i]);}void update(int i, int val) {int delta val-copy[i1];copy[i1] delta;i;for( ;i N; i lowbit(i))v[i] delta;}int sumRange(int i, int j) {return getsum(j)-getsum(i-1);}int getsum(int i){int ans 0;i;for(; i 0; i- lowbit(i))ans v[i];return ans;}//树状数组int lowbit(int m){return m(-m);}
};60 ms 18.8 MB
