前缀和与差分有何区别？

本文共计1290个文字，预计阅读时间需要6分钟。

持续创新，加速成长！这是参与挖金日新计划+10月文献挑战的第32天，点击查看活动详情+1、一维数组的前缀和+对于数列a1,a2,a3,a4……an，前缀和Si就是第i项的代数和。

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第32天，点击查看活动详情

1、一维数组的前缀和

对于一个数列 a1,a2,a3,a4····an，前缀和Si就是前i项的代数和。 所以在用数组储存数列的时候我们不使用a[0]，这样我们就可以令S[0]=0。

#include <iostream> #include <string> using namespace std; const int N = 10000; int n, m; int a[N], s[N] = {0}; int main() { scanf_s("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]); for (int i = 1; i <= n; i++) s[i]=s[i-1]+a[i];//前缀和的初始化 //S[1]=S[0]+a[1];不使用a[0]的好处！！！！ //while (m--) //{ int l, r; scanf_s("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]);//区间和的计算 //} }

2、二维数组的前缀和

和一位数组的思想一样，二维数组的前缀和指的是从（0，0）->（i，j）子组数的和。