[TOC]

1. 区间加法

https://leetcode-cn.com/problems/range-addition

1.1. 输入

• 初始化为0、长度为n的数组arr

• k个三元组updates【k】【startIndex,endIndex,Inc】

  代表k次操作，一次操作表示将arr的【startIndex,endIndex】范围内的数值 +Inc；

1.2. 输出

• 返回k次操作后的数组

1.3. 示例

1.3.1. 示例1

输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

输出: [-2,0,3,5,3]

解释:
初始状态:[0,0,0,0,0]
进行了操作〔1,3,2]后的状态:[0,2,2,2,0]
进行了操作〔[2,4,3]后的状态:[0,2,5,5,3]
进行了操作〔[0,2,-2]后的状态:[-2,0,3,5,3]

1.4. 方法

1.4.1. 方法1 差分数组

差分数组：类似于求解前缀和，给出原数组为d，差分数组为f，那么有f[i] = d[i] - d[i - 1]

差分数组主要支持两种操作：1、区间修改；2、单点查询

思路

1. 给每个操作的arr[start]加inc，和arr[end+1]减Inc;
2. 利用差分数组：f[i] = arr[i] + arr[i-1] 在[1,length-1]区间，进行构建差分数组。

总结：

把每个操作的start位置要增加的统一增加上，同时每个操作的end+1的位置减掉（因为后面差分数组构建时会增加。）

代码

class Solution {
public:
    //正解1  时间复杂度O(n)
    static std::vector<int> getModifiedArray(
        int length,
        std::vector<std::vector<int>> updates)
    {
        std::vector<int> arr(length, 0);
        for (size_t i = 0; i < updates.size(); i++)
        {
            int start = updates[i][0];
            int end = updates[i][1];
            int inc = updates[i][2];

            arr[start] += inc;
            if (end + 1 < length) {
                arr[end + 1] -= inc;
            }

        }

        //2.构建差分数组
        for (size_t i = 1; i < length; i++) {
            arr[i] += arr[i-1];
        }

        return arr;
    }

    //正解2  时间复杂度O(n^2)
    static std::vector<int> getModifiedArray2(
        int length, 
        std::vector<std::vector<int>> updates) 
    {
        std::vector<int> arr(length, 0);
        for (size_t i = 0; i < updates.size(); i++)
        {
            int start = updates[i][0];
            int end = updates[i][1];
            int inc = updates[i][2];

            for (size_t i = start; i <= end; i++)
            {
                arr[i] += inc;
            }
        }

        return arr;
    }
};