前缀和 差分，前缀和与差分模板

文章目录 1 前缀和1.1 什么是前缀和？1.2 例题*1.3 前缀和+hash优化 2 差分2.1 什么是差分？2.2 例题

1 前缀和 1.1 什么是前缀和？

数学表达上他是：
假定有数列： a 0 , a 1 , a 2 . . . a i . . . a n a_0, a_1, a_2...a_i...a_n a0?,a1?,a2?...ai?...an?，则有前缀和 s 0 , s 1 , s 2 . . . s i . . . s n s_0, s_1, s_2...s_i...s_n s0?,s1?,s2?...si?...sn?，其中，
s 0 = a 0 s_0=a_0 s0?=a0?
s 1 = a 0 + a 1 s_1=a_0+a_1 s1?=a0?+a1?
s n = a 0 + a 1 + a 2 + a i + a n s_n=a_0+a_1+ a_2+a_i+a_n sn?=a0?+a1?+a2?+ai?+an?
作用：前缀和是一种重要的预处理，能大大降低查询的时间复杂度。

1.2 例题

以上都是概念，只看概念可能理解的不是很透彻，直接上例题：leetcode 560题

1 暴力解法： O ( n 3 ) O(n^3) O(n3)
略
2 前缀和方法： O ( n 2 ) O(n^2) O(n2)

int preSum[200001];int subarraySum(int* nums, int numsSize, int k){ // 入参检查 if (nums == NULL || numsSize == 0) { return 0; } // sumNums数组记录前缀和 preSum[0] = nums[0]; for (int i = 1; i < numsSize; i++) { preSum[i] = preSum[i - 1] + nums[i]; } int ans = 0; for (int i = 0; i < numsSize; i++) { for (int j = i; j < numsSize; j++) { // i ~ j 的连续子数组和用前缀和计算 // int subSum = i > 0 ? preSum[j] - preSum[i - 1] : preSum[j] 或下面这种形式均可; int subSum = preSum[j] - preSum[i] + nums[i]; if (subSum == k) { ans++; } } } return ans;} *1.3 前缀和+hash优化

C语言不想其他高级语言，对数据结构支撑并没有那么好，手撸复杂hash可能比较困难，幸好现在C语言支撑uthash，能够相对容易的使用hash，感兴趣的同学可以看一看，链接如下：https://blog.csdn.net/fan_h_l/article/details/107241520

还是以上题为例，前缀和+hash优化 的方法能使时间复杂度降低为 O ( n ) O(n) O(n)。由于官方解答叙述的已经很清晰，这里就不赘述了。其表述截图如下，详情键连接，官方还给出了动画。官方题解链接

3 前缀和+hash优化 ： O ( n ) O(n) O(n)

typedef struct Hash_ { int key; int value; UT_hash_handle hh;} Hash;int subarraySum(int* nums, int numsSize, int k){ // 入参检查 if (nums == NULL || numsSize == 0) { return 0; } Hash *head = NULL; Hash *zero = (Hash *)malloc(sizeof(Hash)); zero->key = 0; zero->value = 1; //初始和为0应存入 HASH_ADD_INT(head, key, zero); int ans = 0; int preSum = 0; for(int i=0; i<numsSize; i++){ preSum += nums[i]; Hash * find = NULL; //查找前置和为sum-k的点 int x = preSum - k; HASH_FIND_INT(head, &x, find); if(find!=NULL){ //前置和为sum-k的点,则可以满足其到当前索引i之间的子序列和为k ans += find->value; } Hash * temp = (Hash *)malloc(sizeof(Hash)); temp->key = preSum; temp->value = 1; //将当前i点的前置和sum查找并入表 find = NULL; HASH_FIND_INT(head, &preSum, find); if(find != NULL) { find->value = find->value + 1; } else { HASH_ADD_INT(head, key, temp); } } return ans;} 2 差分 2.1 什么是差分？

差分，是一种和前缀和相对的策略。
这种策略是，令 b i = a i ? a i ? 1 b_i = a_i - a_{i-1} bi?=ai??ai?1? ，即相邻两数的差。
易得对这个序列做一遍前缀和就得到了原来的序列。

2.2 例题

差分的应用上，可能需要稍微结合理论知识点想想，相信你做了一下两个典型题目，就会对差分有一个比较清晰的认知。

1094_拼车
1109_航班预定统计
C语言的解题代码，见我的github仓库。

个人觉得前期掌握前缀和和差分的以上知识，足以面对日常工作所需。
关于前缀和与差分的扩展可以参考了解：https://oi-wiki.org/basic/prefix-sum/。

58792073