[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
一、基本概念
差分算法是前缀和算法的逆运算，可以快速的对数组的某一区间进行计算操作。
例如，有一数列 a[1],a[2],.…a[n]，且令 b[i] = a[i]-a[i-1],b[1]=a[1]，那么就有
a[i] = b[1]+b[2]+.…+b[i] =
a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]，此时b数组称作a数组的差分数组
，换句话来说a数组就是b数组的前缀和数组 例：
原始数组a：9 3 6 2 6 8
差分数组b：9 -6 3 -4 4 2
可以看到a数组是b数组的前缀和数组。
那么现在有一个任务：对数组a区间[left,right]每个元素加一个常数c。这时可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。对于b数组，只需要执行
b[left] += c, b[right+1] −= c
二、leetcode例题
leetcode-1094-拼车
bool carPooling(vector<vector<int>>& trips, int capacity) { vector<int>
origin(1001,0); vector<int> difference(1001,0); int num; int left; int right;
int PrefixSum = 0; // 计算差分数组 for (int i = 0; i < trips.size(); ++i) { num =
trips[i][0]; left = trips[i][1]; right = trips[i][2]; difference[left] += num;
difference[right -1 + 1] -= num; } // 求差分数组的前缀和数组，即原数组 for (int i = 0; i <
difference.size(); ++i) { PrefixSum += difference[i]; origin[i] = PrefixSum; }
// 判断是否有超员 for (int i = 0; i < origin.size(); ++i) { if (origin[i] > capacity)
{ return false; } } return true; }
leetcode-1109-航班预定统计
