区间题库

区间加法

假设你有一个长度为 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]

差分数组

前言:

• 前缀和数组sums[0]、sums[1]……sums[n]的差分序列diff[0]、diff[1]……diff[n-1]就等于原数组，其中diff[i]=sums[i+1]-sums[i]
• 原数组nums[0]、nums[1]……nums[n-1]的差分序列为diff[0]、diff[1]……diff[n-1],其中diff[0]=nums[0]-0、diff[i]=nums[i]-nums[i-1]。对差分数组求前缀和数组，就是原数组
• 差分序列的优势：如果对原数组的一个区间[l,r]上所有元素加value
  • 如果为原数组,原数组上要操作r-l+1次
  • 如果为差分数组，只需要操作两次diff[l]+value和diff[r+1]-value

思路:

• 由题可知，[startIndex,endIndex,inc] 区间里的每一个元素值增加inc ,则可以建立一个初始元素都为0的差分序列diff。对于每一个元素增加inc,即
  • diff[startIndex]+=inc
  • diff[endIndex+1]-=inc
• 差分序列的前缀和即为所求的原数组

:::details 点击查看代码

function getModifiedArray(length, updates) {
    const nums=new Array(length).fill(0);
    for(let item of updates){
        nums[item[0]]+=item[2];
        if(item[1]+1<length){
            nums[item[1]+1]-=item[2];
        }
    }
    for(let i=1;i<length;i++){
        nums[i]+=nums[i-1];
    }
    return nums;
};

:::

性能分析:

• 时间复杂度: O(k+n)
• 空间复杂度: O(n)