通俗易懂的C++前缀和与差分算法图文说明

发布时间：2021-11-07 17:21 所属栏目：61 来源：互联网

导读：目录 1、前缀和2、前缀和算法有什么好处？3、二维前缀和4、差分5、一维差分6、二维差分 1、前缀和前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

目录
1、前缀和2、前缀和算法有什么好处？3、二维前缀和4、差分5、一维差分6、二维差分
1、前缀和
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

加粗样式

2、前缀和算法有什么好处？
先来了解这样一个问题：

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。

我们很容易想出暴力解法，遍历区间求和。

代码如下：

int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--)
{
    int l,r;
    int sum=0;
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++)
    {
        sum+=a[i];
    }
    printf("%d\n",sum);
}
这样的时间复杂度为O(n*m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大提高了运算效率。

具体做法：

首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。

求前缀和运算：

const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i=1;i<=n;i++)
{
    sum[i]=sum[i-1]+a[i];
}
然后查询操作：

scanf("%d%d",&l,&r);
printf("%d\n", sum[r]-sum[l-1]);
对于每次查询，只需执行sum[r]-sum[l-1] ，时间复杂度为O(1)

原理

sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];

（编辑：ASP站长网）