前缀和与差分的笔记

前缀和与差分的笔记"/>

前缀和与差分的笔记

这个题很明显对某一个区间进行加减操作，是一个差分的模版题，只需要注意数据范围，是用int,还是用long long。

#include<iostream>
using namespace std;
int a[5000010];
int sum[5000010];
int n, q, l, r,x;
int main()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];}a[0] = 0;for (int i = 1; i <= n; i++){sum[i] = a[i] - a[i - 1];}for (int i = 1; i <= q; i++){cin >> l >> r >> x;sum[l] += x;sum[r+1] -= x;}for (int i = 1; i <= n; i++){sum[i] += sum[i - 1];}int min = sum[1];for (int i = 1; i <= n; i++){if (min > sum[i]){min = sum[i];}}cout << min;
}

一个简单的前缀和的题只要找到前几项的和=k就输出1如果找不到就输出0；

因为题目中说了是从第i个开始吃不是从头开始，所以只要找到一段连续的子段和为k就行。

#include<iostream>
using namespace std;
using ll = long long;
ll n, k, a[100005],sum[100005];
int main()
{cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}int dex = 0;for (int i = 0; i < n; i++){sum[i] = sum[i - 1] + a[i];}for (int j = 0; j < n; j++){if (sum[j] - sum[j - 1] == k){dex = 1;}}cout << dex << endl;
}

第二个题其实用双指针也可以做同样是进行优化的思路

#include<iostream>
using namespace std;
using ll = long long;
ll n, k, a[100005];int main()
{cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}int left = 0, right = 0;ll sum = 0;int dex = 0;while (right < n){sum += a[right];if (sum == k){dex = 1;break;}while (sum > k){sum -= a[left];left++;}right++;}cout << dex << endl;return 0;
}

双指针其实也是通过限定区间，不断地移动这个区间，来进行判断

1. 定义变量n和k，分别表示食物的种类数和连续不停止吃食物的个数。
2. 定义数组a，用于存储每种食物的数量。
3. 定义变量left和right，分别表示双指针的左右位置，初始值都为0。
4. 定义变量sum，用于记录当前窗口内食物的数量之和，初始值为0。
5. 定义变量dex，用于记录是否满足条件，初始值为0。
6. 使用while循环，不断移动右指针right，并更新sum的值，直到right等于n为止。
   • 在每次移动右指针right时，将a[right]的值加到sum中。
   • 如果当前窗口内食物的数量之和sum等于k，将dex置为1，并跳出循环。
   • 如果当前窗口内食物的数量之和sum大于k，需要移动左指针left，并更新sum的值，直到sum小于等于k为止。
     • 在每次移动左指针left时，将a[left]的值从sum中减去。
7. 输出dex的值，表示是否满足条件。

总结

前缀和一般是对某几个区间的和进行操作的，这样可以降低直接用暴力相加的复杂度，而差分一般是对某个区间进行加减操作，也是降低复杂度的本质是一种优化