目录

前缀和

一维前缀和

查询一个字符串区间[L，R]中有多少个字符d，d为‘a' 或 ’z'

二维前缀和

给定一个二维矩阵，每次给定四个点代表矩阵范围，如何O（1）的求该矩阵内所有数的和(简称矩阵和)

差分

那么考虑一下，对于什么数组求前缀和可以得到原数组呢

差分的定义

作用

Q次操作，每次让下标在区间[L，R]的所有数加上x， 最后让你输出原数组的每个数

力扣5459给你一个目标序列S，让你从全0序列开始做区间+1，问你最少多少次能够造出目标序列

洛谷P4552 [Poetize6] IncDec Sequence

前缀和

一维前缀和

一维前缀和的思想是动态规划，常见的转移为 S[i] = S[i-1] + a[i]，i位置的前缀和等于i-1位置的前缀和加上序列中的a[i]

查询一个字符串区间[L，R]中有多少个字符d，d为‘a' 或 ’z'

对于这个题目，我们可以得出转移式 S[i] = S[i-1] + a[i] == 'a' || a[i] == 'z'，这样一来我们就可以对区间进行O（1）的求出答案

二维前缀和

给定一个二维矩阵，每次给定四个点代表矩阵范围，如何O（1）的求该矩阵内所有数的和(简称矩阵和)

对于这个题目，我们首先思考前缀和的转移，S[i][j]为从从矩阵开头到i，位置内的所有数的和，那么转移式为S[i][j] = S[i-1][j] + S[i][j-1] -S[i-1][j-1] + a[i][j]（左部分和+上部分和减去重合部分加上矩阵当前位置的元素），这样要求四点中矩阵内的和，只需要用右下角的二维前缀和减去左上角的二维前缀和即可

差分

首先对于一个数组，我们做一遍前缀和操作，就可以得到前缀和数组

那么考虑一下，对于什么数组求前缀和可以得到原数组呢

对于这个问题，我们可以对原数组做一个差分操作，那么转移式为

那么我们可以得到b = {1， 1， 2， -1}，我们只需要对此数组做前缀和操作即可得到原数组

差分的定义

 差分是一种与前缀和相对的一种行为，它们互为逆运算，对原数组进行前缀和得到前缀和数组，对原数组进行差分得到差分数组 

作用 O（1）的处理 区间加法

Q次操作，每次让下标在区间[L，R]的所有数加上x， 最后让你输出原数组的每个数

解题思路：

最开始读入原数组，把他变成差分数组，然后对差分数组进行操作，然后最后做一遍前缀和还原 成原数组即可。

思考:为什么对差分数组能做到的O（1）区间加法？

首先我们考虑对差分数组的第i个位置+x，因为我们最终要做前缀和还原数组，所以这个位置+x会影响后面所有的元素，这个x会被前缀和操作往后传递

这样的行为我们称为标记传递，有了这样的思路之后我们在考虑如何让[L，R]的数+x，而后面的地方不受影响呢

所以我们有Q次操作，每次对差分数组打标记，b[l] += x，b[r+1] -= x，最后做前缀和即可实现题目要求，即如下图所示，消除前一个x的影响 

#include
using namespace std;

#define ll long long
const ll maxn = 1e9 + 5;

int main()
{
    //Q次操作
    int q;
    //原数组，差分数组，前缀和数组
    int a[11] = {0}, b[11] = {0}, s[11] = {0};
    cin >> q;
    //先求出原数组的差分数组
    for(int i = 1; i <= 10; i++)
    {
        if(i == 1)b[i] = a[i];
        else b[i] = a[i] - a[i-1];
    }
    while(q--)
    {
        int l, r, x;
        cin >> l >> r >> x;
        //对差分数组做传递标记
        b[l] += x;
        b[r+1] -= x;
    }
    //最终求出前缀和数组
    for(int i = 1; i <= 10; i++)
    {
        s[i] = s[i-1] + b[i];
        cout << s[i] << " ";
    }
    return 0;
}

力扣5459给你一个目标序列S，让你从全0序列开始做区间+1，问你最少多少次能够造出目标序列

题目链接：无

给你一个目标序列S，让你从全0序列开始做区间+1，问你最少多少次能够造出目标序列

解题思路：

假如目标序列S = {3， 6， 4， 2， 7}，那么我们得到差分数组b = {3， 3， -2， -2， 5}，由于题目给出了每次只能区间+1，这对应着，我们至少在i的位置需要有一个b[i]次的操作，所以我们只要统计b数组内的正整数即可

#include
using namespace std;

#define ll long long
const ll maxn = 1e9 + 5;

int main()
{
    int a[105] = {0}, b[105] = {0};
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    //对数组进行差分
    for(int i = 1; i <= n; i++)
    {
        if(i == 1)b[i] = a[i];
        else b[i] = a[i] - a[i-1];
    }
    //求差分数组中的正数和
    for(int i = 1; i <= n; i++)
    {
        if(b[i] > 0)ans += b[i];
    }
    cout << ans;
    return 0;
}

洛谷P4552 [Poetize6] IncDec Sequence

题目链接：洛谷P4552 [Poetize6] IncDec Sequence

解题思路：

对于给出的数组我们进行差分操作，得到一个序列，根据差分的性质可以得出，每一个当前位置的元素会对后产生传递影响，所以题目要求将所有的数变为一样，我们只需要将b[2]到b[n]的位置全部变为0即可，我们对差分数组的[L，R]进行操作时，是对L做一个操作，R+1进行反操作，这样会影响还原原数组，然而对于差分数组本身是没有影响的，这样的操作只会改变L和R+1，所以计算出差分数组2-N的正数和与负数和，题目给出的操作为[L，R]可以+1或-1，所以每一次都是+1对应着-1，第一问，那么我们的最小操作次数就是正数与负数绝对值的最大数，第二问，因为我们最大数会比最小数多出来几次操作，我们可以将这个操作算到b[1]上，又因为b[1]不操作也算一次，所以第二问多少种可能就是正数与负数绝对值的差值+1

#include
using namespace std;

#define ll long long
const ll maxn = 1e5 + 5;

int main()
{
    ll n, up = 0, down = 0;
    ll a[maxn];
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    for(int i = 2; i <= n; i++)
    {
        //对差分数组的第二项到最后一项进行正数和负数的分别相加
        if(a[i] - a[i-1] > 0)up += a[i] - a[i-1];
        else down -= a[i] - a[i-1];
    }
    //最少操作次数是二者的最大值，最多可能是二者的差
    cout << max(up, down) << endl << max(up, down)-min(up, down)+1;
    return 0;
}