差分&前缀和

前缀和的应用场景是,需要对某个区间[i...j]频繁查询累计和,避免每次查询都遍历这个区间。

差分数组的应用场景是,需要对某个区间[i...j]频繁地加或减某一值,避免每次都遍历这个区间。

dif数组本质是对[l,r]区间,dif[l]+=x,dif[r+1]-=x;

使用n的dif数组为什么要判断?
好吧,这样说可能有人没懂,我们按照题目的例子推演一次:

初始航班预订数量数组 answer = [0,0,0,0,0],差分数组d = [0,0,0,0,0]
当遍历到bookings[0] = [1,2,10]的时候,差分数组第1位加10,第3位减10,变成d = [10,0,-10,0,0]
同理,当遍历到bookings[1] = [2,3,20]的时候,差分数组变成d = [10,20,-10,-20,0]
当遍历到bookings[2] = [2,5,25]的时候,差分数组变成d = [10,45,-10,-20,0],第6位要减25,我们也不需要了
最后计算answer数组的值,answer[0] = d[0] = 10,answer[1] = d[1] + answer[0] = 45 + 10 = 55,answer[2] = d[2] + answer[1] = -10 + 55 = 45...
最最后发现,只申请一个数组表示d[]和answer[]就可以了,over!

原文地址:https://www.cnblogs.com/purexww/p/14418480.html