差分数组的应用¶
问题¶
题目见 
简单说就是多次对数组任意区间内的数据进行加减,最后要能得出数组里任意位置的值.¶
比如初始数据[0, 0, 0, 0] 对[1, 4]加2,得到[2, 2, 2, 2]. 再对[2,3]减1,得到[2, 1, 1, 2].
如果区间范围比较大.暴力遍历效率太低,不可能每次修改都去遍历整个区间.
可做一个差分数组. 例如对于包含实际值的数组a: 1 3 99 50 12 20 可以有一个差分数组d: 1 2 96 -49 -38 8
限定d的每个值是a中相对的元素减去