[TOC]

一、题目描述

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

示例:

输入: 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-addition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题算法

1. 暴力法

思路：

由于题目说了，每个操作都是修改原数组中的一部分，那我们直接模拟整个操作即可。
简单粗暴，由于最坏情况下每次操作都可以操作整个数组，总操作k次，因此时间复杂度 $O(nk)$ ，空间复杂度 $O(n)$ 。
提交后会卡在最后一组测试数据，超时。

代码：

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

2. 区间求和

思路：

由于解法1超时，我们便来想想有没有什么更好的解决方案。
我们注意到，题目要求的是返回k次操作后的数组，而不需要每操作一次都返回数组。也许，我们不需要每一次都模拟操作过程？
我们又注意到，解法1的时间复杂度是 $O(nk)$ ，这里面显然k是无法减小的，那我们只能在n上想想办法。而比 $O(n)$ 更低的复杂度，常见的无非 $O(log_2n)$ 和 $O(1)$ ，其中 $O(log_2n)$ 一般都与二分挂钩，这里好像没有办法使用，要是有谁能想到，欢迎在下方评论。

因此，我们的目标就变成了有没有办法把每次操作的时间复杂度从 $O(n)$ 降到 $O(1)$ ？
暂定我们的目标为将复杂度降低至 $O(1)$ ，那么我们知道在 $O(1)$ 的复杂度下，能做的无非只是几条顺序语句，这样的限制有助于我们缩小思考空间。

或许，我们可以只在每次操作的两个端点做一些什么，就能表示这段区间内所有元素都加上val？
一种自然的思路是我可不可以在区间的左端点start处记录下一个val，表示从start起，右边的所有元素都加上val。
但这样在end右侧的元素也都被加上了val，与题意不符。
为了修正这个问题，我们可以在end + 1的位置加上-val。这样由于end右侧的元素先加上val，再加上-val，等于没有变化。

嗯……好像这种思路有搞头诶？

那么接着，我们得考虑一下，经过k次操作之后，我们用来保存操作结果的数组变成了什么样？假设用来保存操作累计结果的数组为arr，由于位置i上的元素表示从位置i起的每一个元素都要加上arr[i]。因此我们只要 $\sum^i_{j=0}a_j$ 便可以得到a[i]上的元素在k次操作后实际的累加值。该操作只需 $O(n)$ 的时间复杂度便可以完成。最后由于初始值每个元素都是 $0$ ，因而累加值数组arr便是我们要的结果。

于是，总时间复杂度由 $O(nk)$ 被优化到了 $O(n+k)$ 。

代码：

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> arr(length, 0);
        for (auto &update : updates) {
            auto start = update[0], end = update[1], val = update[2];
            arr[start] += val;
            if (end < length - 1)
                arr[end + 1] -= val;
        }
        partial_sum(arr.begin(), arr.end(), arr.begin());
        return arr;
    }
};

3. 区间求和（一个小的优化技巧）

思路：

解法2的效率已经可以了，但其实还有一个编程技巧上的小的优化空间。

我们注意到，解法2在循环中有一个if。虽然可以通过分支预测来提高效率，但明显的，它存在着打断CPU流水线的可能性。我们可以通过使得arr的长度为length + 1来取消掉这个if分支。

在总时间复杂度不变的情况下，执行用时由解法2的148ms变为100ms。

代码：

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> arr(length + 1, 0);
        for (auto &update : updates) {
            auto start = update[0], end = update[1], val = update[2];
            arr[start] += val;
            arr[end + 1] -= val;
        }
        arr.pop_back();
        partial_sum(arr.begin(), arr.end(), arr.begin());
        return arr;
    }
};

370.区间加法

370.区间加法

一、题目描述

二、解题算法

1. 暴力法

2. 区间求和

3. 区间求和（一个小的优化技巧）