307. 区域和检索 – 数组可修改（JS实现）
307. 区域和检索 – 数组可修改（JS实现）
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 函数的调用次数是均匀分布的。
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
2 思路
这道题用动态规划的方法来做即可，在更新数组元素值时，也要更新dp数组
3代码
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.d = [];
this.nums = nums;
let sum = 0;
for (let i=0; i<nums.length; i++) {
sum += nums[i];
this.d[i] = sum;
}
};
/**
* @param {number} i
* @param {number} val
* @return {void}
*/
NumArray.prototype.update = function(i, val) {
let diff = val – this.nums[i];
for (let j=i; j<this.d.length; j++) {
this.d[j] += diff;
}
this.nums[i] = val;
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.d[j] – (i > 0 ? this.d[i-1] : 0);
};
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* obj.update(i,val)
* var param_2 = obj.sumRange(i,j)
*/