感谢@HsKr 纠正了版式上的一些问题QWQ。
区间问题中，若只涉及区间加/区间求和，那么可以用前缀和与差分高效的完成。
例题：给定一个长度为 \(n\) 的序列 \(a\) ，给出 \(m\) 次操作，每次操作询问一段区间 \([l,r]\) 的值。
暴力当然可以做，但是可以利用前缀和 \(\mathcal{O}(1)\) 查询！
设 pre[i] 表示 1~i 的和，那么这个 pre 数组可以递推出来。代码大概长成这样：
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pre[i]=pre[i-1]+a[i]; //1~i-1的和加上当前数字就是1~i的和
}如果仍感到难以理解可以结合下面这个表：
a: 1 2 3 4 5 6 7 8 9
pre: 1 3 6 10 15 21 28 36 45现在我们手里有了 pre 数组，我们可以拿她做什么事呢？
如果我们需要查询 \([l,r]\) 的和，那么我们可以直接 pre[r]-pre[l-1] 。
道理呢？
放个图：
红色的那部分就是 pre[r] ，即 \([1,r]\) 的和
然后我们把 \([1,r]\) 的和减去 \([1,l-1]\) 的和（即蓝色的部分），得到的就是 [l,r] 的和了！
然后很多人会有一个疑问：为什么减去的不是 pre[l] 而是 pre[l-1] 呢？的确，从图上看的不是很清楚，那么请回顾 pre 数组的定义：
设 pre[i] 表示 1~i 的和
1~i 的和，也就是说，pre[l] 的值是加上了 a[l] 的 ，那么如果减去 pre[l] ，也就同时减去了 a[l] ，计算的就是 \([l+1,r]\) 的和了！（理解这一点很重要，待会差分的时候也会遇到同样的问题）。
二维前缀和用于维护矩形面积。
题目意思就是说维护一个面积为 \(5001\times 5001\) 的矩形，\(n\) 个点 \((x_i,y_i)\) 会有一个权值，要求找出一个边长为 \(R\) 的正方形，使得这个正方形里所有点的权值之和最大。
记 \(sum_{x,y}\) 为面积为 \(x\times y\) 的矩形内所有权值之和，那么我们也可以快速递推出来（其实并不快==）
for(int i = 1; i <= n; i++)
{
int x, y, v;
cin >> x >> y >> v;
sum[x + 1][y + 1] += v;
}
//DEBUG;
for(int i = 1; i <= 5001; i++)
for(int j = 1; j <= 5001; j++)
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];注意上面现把 \(sum_{x,y}\) 当作一个点来计算，然后在下一个循环时直接拿 \(sum_{x,y}\) 当作 \(a_{x,y}\) 的大小递推。由于题目中 \(x,y\) 可能等于 0，所以在实际计算时要整体下移
什么意思呢？看图理解：
如图所示，我们现在要利用 \(sum_{x,y}\) 得到我们想要的这个矩形的值，那么这个值可以怎样拼凑呢？
首先就是 \(sum_{x,y-1}\)
然后是 \(sum_{x-1,y}\)
别忘了加上本身的权值 \(sum_{x,y}\) ！（注意，此时 \(sum_{x,y}\) 未被更新，保存的仍相当于 \(a_{x,y}\) 但是之前的 sum 值都是更新过的，可以直接拿来用）。
对了么？
其实还不对，观察我们加上的区域：
发现绿色部分，即 \(sum_{x-1,y-1}\) 被重复加了两次！好办，减去即可。完整的递推式就是：
\[ sum_{x,y}=sum_{x,y-1}+sum_{x-1,y}+sum_{x,y}-sum_{x-1,y-1} \]
现在我们手握重权，回到例题：
要求找出一个边长为 \(R\) 的正方形，使得这个正方形里所有点的权值之和最大。
那么考虑从 \((R,R)\) 开始枚举（因为最少只能是左上角的 \(R\times R\) 的矩形），每次用 sum 数组更新答案。这个答案怎么更新呢？
如图：
我们希望求出红色部分的权值和，那么我们可以拿整个大矩形，减去绿色的部分得到。那么大概可以得到：
\[ sum_{x,y}-sum_{x-r,y}-sum_{x,y-r} \]
但是仔细观察可以发现，在下图中，蓝色的部分被减去了两次！（\(sum_{x-r,y}\)那个矩形和\(sum_{x,y-r}\)这两个子矩形重合的部分）
很好办，再把这个矩形的权值和加上即可，所以最后正确找到这个红色矩形的递推式就是：
\[ sum_{x,y}-sum_{x-r,y}-sum_{x,y-r}+sum_{x-r,y-r} \]
写成代码就是
int ans=-(1<<30); //ans记录答案（最大值）
for(int i = r; i <= 5001; i++)
for(int j = r; j <= 5001; j++)
ans = max(ans, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]);完整的AC代码就是
#include <iostream>
#include <stdio.h>
#include <math.h>
#define DEBUG printf("This is OK\n")
using namespace std;
int n, r, sum[5003][5003];
int main()
{
cin >> n >> r;
for(int i = 1; i <= n; i++)
{
int x, y, v;
cin >> x >> y >> v;
sum[x + 1][y + 1] += v;
}
//DEBUG;
for(int i = 1; i <= 5001; i++)
for(int j = 1; j <= 5001; j++)
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
//DEBUG;
int ans=-(1<<30);
for(int i = r; i <= 5001; i++)
for(int j = r; j <= 5001; j++)
ans = max(ans, sum[i][j] - sum[i - r][j] - sum[i][j - r] + sum[i - r][j - r]);
cout << ans <<endl;
return 0;
}注这题卡空间，数组不能开太大。
继续刚刚那个问题，如果不需要查询区间和，而需要把区间加上一个值怎么办办呢？
设 c[i] 表示 a[i] 与 a[i-1] 的差，那么这个 c 数组也可以快速递推出来
for(int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i]-a[i-1];
}看看 c 数组长啥样
a: 1 2 3 4 5 6 7 19
c: 0 1 1 1 1 1 1 12c 数组也就是差分数组
不难看出，差分与前缀和互为逆运算
现在我们手握 c 数组，如何利用她来干事情呢？
如果要把 \([l,r]\) 加上 x ，那么我么可以把 c[l]+x，c[r+1]-x
之所以这么干，道理是 \(a_i(l\le i\le r,i\in \mathbb{Z})\) 进行操作后，我们不去更改 a 数组本身，而是去改变她的差分数组 c 。对这个序列 a 的影响从 l 开始，那么也就是从 l 起，a 中的每一个数都比前一个多 x ，所以把 c[l] 加上 x；这个影响到哪里结束呢？也就是从 a[r+1] 开始，值不会被改变，那么就意味着影响结束了。为了避免前面的改动对后面造成的影响，我们强制把第 r+1 个位置减去 x ，这样一来，就抵消了前面的操作。
用刚刚那个表举个例子，如果要把 \([3,5]\) 内的值都加上 1，那么：
原本：
a: 1 2 3 4 5 6 7 19
c: 1 1 1 1 1 1 1 12
修改后的c：
c: 1 1 2 1 1 0 1 12如何递推出修改后的 a 呢？很简单，利用原来的 a 序列不断加上 c 的值即可
原本：
a: 1 2 3 4 5 6 7 19
c: 1 1 1 1 1 1 1 12
修改后的c：
c: 1 1 2 1 1 0 1 12
还原a：
a: 1 2 4 5 6 6 7 19似乎挺奇怪的。例题：[洛谷P3397]地毯
一个很朴素的想法是，每当输入一组地毯的坐标时，直接 \(\mathcal{O}(n^2)\) 更新答案（i.e. 把答案所有在这个范围内的都+1）.
参考代码：
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m,a[1001][1001];
int main()
{
cin>>n>>m;
while(m--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
a[i][j]++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
puts("");
}
return 0;
}此题数据范围太水，这段代码确实能通过；考虑如何优化：记一个二维数组 pre 为差分数组，一开始都为0（没有任何地毯覆盖）。
当输入一组数据 \((x_1,y_1),(x_2,y_2)\) 时，我们扫描 x1 ~ x2（每一行），把每一行对应的列做一个差分。
e.g. 设我们要覆盖 $ a_{i,j}(2\le i,j \le5, i,j\in\mathbb{Z})$ 这个子矩阵，那么有：
一开始
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
差分：
0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0可以看出差分的方法是不变的，只不过变成了每一次做 \(x_2-x_1\) 次差分！
那么代码也就呼之欲出了！
while(m--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=x1;i<=x2;i++)
{
pre[i][y1]++;
pre[i][y2+1]--;
}
}同样的，在输出时分行处理即可。这里有一个技巧：由于一开始的大矩阵也都是 0 ，最后可以直接用 pre 数组递推，从而省区了部分空间。
写法一：
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m,pre[10001][10001],a[10001][10001];
int main()
{
cin>>n>>m;
while(m--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=x1;i<=x2;i++)
{
pre[i][y1]++;
pre[i][y2+1]--;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=a[i][j-1]+pre[i][j];
cout<<a[i][j]<<" ";
}
puts("");
}
return 0;
}写法二：
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m,pre[10001][10001],a[10001][10001];
int main()
{
cin>>n>>m;
while(m--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=x1;i<=x2;i++)
{
pre[i][y1]++;
pre[i][y2+1]--;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
pre[i][j]+=pre[i][j-1]; //直接用 pre 数组推
cout<<pre[i][j]<<" ";
}
puts("");
}
return 0;
}（题目有点问题，不是是对于“第i段铁路，需要花Ci博艾元的工本费购买一张IC卡，然后乘坐这段铁路一次就只要扣Bi(Bi<Ai)元。”而是“对于第i段铁路，需要花Ci博艾元的工本费购买一张IC卡，然后乘坐这段铁路一次就只要Bi(Bi<Ai)元。”）
一个显而易见的思路是，对于走过的每一条路，看看使用哪种方法（直接用纸质票还是买 IC 卡）更优。但是注意到一段线路会出现多次，那么就要线记录这一段线路走了多少次再更新答案。
如果直接暴力搞会超时，同上，pre再这题中既是记录次数的数组也是差分数组（这是因为一开始都是0，那么次数和差分两个数组就可以合并。这是很常用的一个技巧）。
然后每次取区间的左端点、右端点，差分即可。然后都弄完后跑一遍前缀和，最后拿着 pre 去找答案就好了。
具体看代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#define ull unsigned long long
using namespace std;
ull n,m,p[1000010],ans,pre[1000019];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>p[i];
for(int i=1;i<m;i++)
{
ull l=min(p[i],p[i+1]);
ull r=max(p[i],p[i+1]);
//数据有可能反过来
pre[l]++;
pre[r]--;
}
for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
//差分数组的前缀和就是每一段出现的次数
for(int i=1;i<n;i++)
{
ull a,b,c;
cin>>a>>b>>c;
ans+=min(a*pre[i],b*pre[i]+c);
//用更优的方案
}
cout<<ans<<endl;
return 0;
}练习：
提示：前缀和+枚举+优化
原文：https://www.cnblogs.com/BlueInRed/p/12501868.html