C前缀和与差分如何使用

前缀和

前缀和是指将一个数组中的元素从前往后依次累加的过程，并把结果储存在另一个数组中。在实际应用中，前缀和可以用于优化一些算法，如区间求和、区间和的最大/最小值等。下面以一个区间求和的问题为例：

#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], s[N];   //a数组存储原始数据，s数组存储前缀和

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    //计算前缀和
    for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];

    while(m--)
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;    //区间求和
    }

    return 0;
}

差分

差分是一种与前缀和相反的操作。差分数组d[i]表示原始数组a[i]与a[i-1]的差值。通过差分数组d[i]来对原始数组a[i]进行修改，最后可以通过求前缀和得到新的数组。差分的应用场景较少，主要用于某些特定场景下的优化。下面以区间修改问题为例：

#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], d[N];   //a数组存储原始数据，d数组存储差分数组

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    //差分预处理
    for(int i = 1; i <= n; i++) d[i] = a[i] - a[i-1];

    //区间修改
    while(m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        d[l] += k;
        d[r+1] -= k;
    }

    //求前缀和得到新的数组
    for(int i = 1; i <= n; i++) d[i] += d[i-1];
    for(int i = 1; i <= n; i++) cout << d[i] << ' ';

    return 0;
}

前缀和和差分的关系

差分本身并不常用，但它与前缀和有着紧密的联系。前面已经提到过，差分数组d[i]表示原始数组a[i]与a[i-1]的差值。因此，对差分数组求一遍前缀和即可得到原始数组a[i]。同样地，对原始数组a[i]求一遍前缀和也可以得到差分数组d[i]。这两者之间的转换可以用于一些求解区间和的优化问题。

例如，如果需要对原始数组a[i]进行区间加法操作，可以转化成对差分数组d[i]的两个位置进行加减操作。再对差分数组求一遍前缀和，即可得到新的数组。代码如下：

//区间加
void add(int l, int r, int k)
{
    d[l] += k;
    d[r+1] -= k;
}

//求新的数组
for(int i = 1; i <= n; i++) s[i] = s[i-1] + d[i];

总结

前缀和和差分是两个简单有效的数组处理技巧。前缀和可以用于优化一些求解区间和的问题，差分则可以用于优化某些区间修改问题。两者之间还可以通过前缀和数组和差分数组的相互转换进行一些性质的优化。需要注意的是，在使用前缀和和差分时，要注意边界问题，以及差分数组的初始值应该为0。