307. 区域和检索 - 数组可修改（JS实现）

以你之姓@ 2022-11-27 15:58 109阅读 0赞

## 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) */