本文章原出处：chicago01.top，转载不需说明，随意转载

前缀和基本概念

普通(一维，二维)前缀和:

a[1],a[2],a[3].....a[n]
s[i] = a[i] + a[i-1]...a[2] + a[1]

a[3] + a[4]...a[14] + a[15] = s[15] - s[3-1]
s[l,r] = s[r] - s[l-1]

二维前缀和:

假设在一个二维平面上，每个点具有一定的权值，我们要计算点（2，2）到（8，4）的权值和。

[HTML_REMOVED]

首先我们要找到这么几块面积：

我们可以发现，我们所要求的黄色区域，就是黑色 - 绿色 - 粉色 + 青色。

好了，知识都听少的，看例题。

例1激光炸弹

一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。

现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个边长为 RR 的正方形的边必须和x，y轴平行。

若目标位于爆破正方形的边上，该目标不会被摧毁。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来NN行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标，y坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

0<N≤10000
0≤Xi,Yi≤5000

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

题解：

这很明显就是一道二维前缀和的问题了，找区域最值。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5010;
int g[maxn][maxn];

int main(void)
{
    int N,R;
    cin >> N >> R;

    int n = R, m = R;

    for(int i = 0,x,y,w;i < N;++i)
    {
        cin >> x >> y >> w;
        x++,y++;
        n = max(n,x);
        m = max(m,y);
        g[x][y] += w;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1;j <= m; j++)
            g[i][j] += g[i-1][j] + g[i][j-1] - g[i][j];

    int ans = 0;
    for(int i = R;i <= n;i++)
        for(int j = R;j <= m;j++)
            ans = max(ans,g[i][j]-g[i-R][j]-g[i][j-R]+g[i-R][j-R]);

    cout << ans ;

    return 0;
}

差分基本概念

a[1],a[2],.…a[n]
b[i]=a[i]-a[i-1],b[1]=a[1]

a[i]=b[1]+b[2]+.…+b[i]
    =a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]

由此可见，原数组就是差分数组的前缀和。我们可以举个例子：

原始数组：9  3  6  2  6  8
差分数组：9 -6  3 -4  4  2

现在有一个任务，在区间$[l,r]$上加一个常数c。

我们可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。显然可得出公式：$b[l] += c,b[r + 1] -= c$ 。

例2IncDec序列

给定一个长度为 $n$ 的数列 $a1,a2,…,an$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数$n$。

接下来$n$行，每行输入一个整数，第$i+1$行的整数代表$ai$。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

$0<n≤10^5$,
$0≤ai<2147483648$

输入样例：

4
1
1
2
2

输出样例：

1
2

题解：

要使最后的数都一样，那么$b$数组中的$b2=>bn$  一定全 $0$

因为

    b2 = a2-a1;
    b3 = a3-a2;
    ......
    bn = an-an-1;

如果全0 的话， $a1=a2=a3=…=an$

所以我们可以用贪心的思想，来使得b中所有数变成零。 我们知道我们在做b[L]++,b[R+1]--;操作的时候，要找两个数配对，那么 负数++，正数--，是不是就最快了。 但是最终结果可能依然不是全 $0$ 的，因为 $abs(sum(正数)) 可能 ！= abs(sum(负数))$

所以，我们可以 让最后不等于0 的数全和 $b1|| bn+1$来换。

$ans1 = min(pos,neg)+abs(pos-neg)$

$ans2 = abs(pos-neg)+1$

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int num[maxn];

inline void init()
{
    int n = 0;
    cin >> n;

    for(int i = 1;i <= n;++i)
        cin >> num[i];

    for(int i = n;i > 1;--i)
        num[i] -= num[i-1];
}

inline void frond()
{
    long long pos = 0,neg = 0;
    for(int i = 2;i <= n;++i)
    {
        if(a[i] > 0) pos += a[i];
        else neg -= a[i];
    }

    cout << min(pos,neg) + abs(pos - neg) << endl << abs(pos - neg) + 1;
}

int main(void)
{
    init();

    frond();

    return 0;
}