> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/201-400/370.-qu-jian-jia-fa.md).

# 370.区间加法

#### [370.区间加法](https://leetcode-cn.com/problems/range-addition/)

题目大意:给一个二维数组,其中每个数组长度为3,包含了更新信息.

## 一、直接法

解题思路:硬算即可.

```cpp
class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> res(length);
        for (auto u : updates) {
            for (int i = u[0]; i <= u[1]; i++) {
                res[i] += u[2];
            }
        }
        return res;
    }
};
```

## 二、差分数组

这才是本题要考察的方法，差分数组算法参考<https://labuladong.gitee.io/algo/2/21/52/>

简单来说用一个`diff`数组记录nums前后元素的差值，即`diff[i] = nums[i] - nums[i-1], i >= 1`，当`nums`的`i~j`区间整体加x（某个数）时，`i~j`区间`diff`是不变的，只有两端的`diff`改变，利用这个性质减少运算量，最后再用`nums[i] = nums[i-1] + diff[i]`还原

```python
class Solution:
    def rangeAddition(self, length, updates):
        diff = [0] * length	 #差分数组，因为初始原数组全0，因此差分也是0
        #进入迭代
        for update in updates:
            i, j, val = update[0], update[1], update[2]
            diff[i] += val
            if j+1 < length:	#注意当j+1越界时的处理
                diff[j+1] -= val
        #迭代完成后还原数组
        res = [0] * length
        res[0] = diff[0]
        for i in range(1, length):
            res[i] = res[i-1] + diff[i]
        return res
```