差分数组定义:diff[i] = arr[i] - arr[i-1],其中约定arr[-1] = 0;区间[l,r]统一加v的操作规则为:diff[l] += v,若r+1 < 数组长度则diff[r+1] -= v,最终通过差分数组求前缀和得到原数组。
最终得到的差分数组为[3,2,1,-3,-2],原数组最终结果为[3,5,6,3,1]
使用差分数组处理上述3次区间操作的时间复杂度为O(n)(n为数组长度)
差值分析算法最适合处理单点更新、区间查询的高频操作场景
执行第一次区间[1,3]加2的操作时,仅需要修改差分数组下标1和3两个位置的取值