差分

坑不只占了一年么

感谢Herself32推荐的模板题

差分以前缀和为基础（前缀差？），可以实现O(1)修改，O(n)查询。

例题 洛谷P2367 语文成绩

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

//这又跟神器有什么关系呢？神说：呵呵。

//因为n和p的范围比较大 建议C++选手使用scanf读入.

//同时建议写读入优化....

//最后一个点，亲测pas读入800+ms，c/C++的scanf 1200+ms，所以这个点的时限改为2s

输入输出格式

输入格式：

第一行有两个整数n，p，代表学生数与增加分数的次数。

第二行有n个数，a1~an，代表各个学生的初始成绩。

接下来p行，每行有三个数，x，y，z，代表给第x个到第y个学生每人增加z分。

输出格式：

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例

输入样例#1：

3 2
1 1 1
1 2 1
2 3 1

输出样例#1：

2

说明

对于40%的数据，有n<=1000

对于60%的数据，有n<=10000

对于80%的数据，有n<=100000

对于100%的数据，有n<=5000000，p<=n，学生初始成绩<=100，z<=100

解法

cin + 差分

什么是差分

我们有两个数组a[5] = {1,3,5,2,4};，A[5]。

我们让A存储a数组中，每相邻两个数的差。即A[i] = a[i] - a[i - 1]

于是 两个数组对应如下

数组	column1	column2	column3	column4	column5
a	1	3	5	2	4
A	1	2	2	-3	2

把a[2]到a[4]都加5，再预处理A[i] = a[i] - a[i - 1]

于是 两个数组对应如下

数组	column1	column2	column3	column4	column5
a	1	8	10	7	4
A	1	7	2	-3	-3

我们发现A数组中只有A[2]和A[4+1]的数变化。（等式的性质）

想想为什么吧

于是，我们反推，只O(1)修改A数组的两个值，之后便可O(n)咨询出a数组的值。

修改

A[l] += k;
A[r + 1] -= k;

查询

for (int i = 1; i <= n; i++)
{
    a[i] = a[i - 1] + A[i];
    cout << a[i] << " ";
}

模板代码

#include <iostream>
using namespace std;
int a[1000], A[1000];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        A[i] = a[i] - a[i - 1];
    }
    char cmd;
    while (true)
    {
        cin >> cmd;
        switch (cmd)
        {
        case 'p':
            int l, r, k;
            cin >> l >> r >> k;
            A[l] += k;
            A[r + 1] -= k;
            break;
        case 'v':
            for (int i = 1; i <= n; i++)
            {
                a[i] = a[i - 1] + A[i];
                cout << a[i] << " ";
            }
            cout << endl;
            break;
        case 's':
            return 0;
        }
    }
}