【Lintcode】903. Range Addition

题目地址：

https://www.lintcode.com/problem/range-addition/description

给定一个长度为$n$的零数组$A$，再给定若干次更新，每次更新由三元组组成，$(a,b,x)$，表示将$A[a:b]$的所有元素增加$x$。问更新完成之后$A$变成了什么。

思路是差分数组。设$d[i]=A[i]?A[i?1]$，则每次更新的时候，相当于执行对$d[a]$增加了$x$，而对$d[b+1]$减少了$x$。这样就可以将每次更新操作的时间复杂度降为了$O(1)$。最后只需要对$d$求前缀和就能还原回$A$了。代码如下：

public class Solution {
    /*** @param length: the length of the array* @param updates: update operations* @return: the modified array after all k operations were executed*/public int[] getModifiedArray(int length, int[][] updates) {
    // Write your code hereint[] diff = new int[length];for (int[] update : updates) {
    diff[update[0]] += update[2];if (update[1] + 1 < length) {
    diff[update[1] + 1] -= update[2];}}for (int i = 1; i < length; i++) {
    diff[i] += diff[i - 1];}return diff;}
}

时间复杂度$O(n+u)$，$n$为数组长度，$u$为更新次数，空间$O(1)$。