资料
题目
- 【模板】前缀和
- 【模板】差分
- 【模板】二维前缀和
- 模板】二维差分
前缀和算法
前缀和可以简单理解为「数列的前n项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。
定义一个数组 $a_i$ 为任意数字组成的集合，存储其前n项和 $O(n)$。
$$
P_i=\sum_{j=1}^ia_i=P_{1-1}+a_i
$$
对前n项和的求和运算拥有可加/减性。
$$
sum[1,k]+sum[k+1,n]=sum[1-n]
$$
所以可以通过这个性质，一次计算 l-r 闭区间的数字之和。
$$
ans=sum[l,r]=sum[1,r]-sum[1,l-1]=P_r-P_l
$$
const int N = 1e5 + 9;
int n, q, l, r, map[N];
ll prefix[N]; // 存储前缀和
// https://oj.eriktse.com/problem.php?id=1049
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> map[i]; // 先随便存一下数字
for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + map[i]; // 存储前缀和
cin >> q; // q次询问
while (q--) {
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << endl;
// 一次计算，输出 l、r 闭区间范围的和
}
}差分算法
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
💡 差分数组是静态的，因此不能解一边循环一边修改的问题，只有修改完成后，使用复杂度 $O(1)$ 进行询问。
差分数组 diff[N]：良好的修改性质，可以对一个范围进行修改。
$$
d_i=\begin{cases}
a_i-a_{i-1}\,&i\in[2,n] \
a_1\,&i=1
\end{cases}
$$
借此进行修改后，通过前缀和还原 $a_i$ 实现数组 $a_i$ 的特定区间修改。
- 通过前缀和还原出 $a_i$
$$
\sum_{j=1}^id_j=d_1+d_2+d_3+\cdots+d_i=(\bcancel{a_1}-a_0)+(\bcancel{a_2}-\bcancel{a_1})+(\bcancel{a_3}-\bcancel{a_2})+\cdots+(\bcancel{a_{i-1}}-\bcancel{a_{i-2}})+(a_{i}-\bcancel{a_{i-1}})=0+a_i=a_i
$$
- 后缀区间修改
- 对 $d_l+x$ 则会造成 $a_{l+1}+x,a_{l+2}+x,\cdots,a_n+x$
- 再对 $d_{r+1}-x$ 则会造成 $a_{r+1}-x,a_{r+2}-x,\cdots,a_n-x$
- 从事实现将数组 $a_i$ 中 [l-r] 区间内的元素进行 +x 操作
修改+询问的整体流程：输入数组 $a_i$ → 定义差分数组 $d_i=a_i-a_{i-1}$ → 对 $d_i$ 进行修改 → 对 $d_i$ 使用前缀和 → 还原 $a_i$ → 在进行求和询问。
const int N = 1e5 + 9;
ll n, map[N], diff[N], prefix[N];
// https://oj.eriktse.com/problem.php?id=1050
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> map[i];
for (int i = 1; i <= n; ++i) diff[i] = map[i] - map[i - 1]; // 求差分数组
int m;
cin >> m;
while (m--) { // m次修改操作
int l, r, x;
cin >> l >> r >> x;
// 后缀区间修改 给 [l,r] 进行 +x 修改
diff[l] += x; // 修改 [l,n] +x
diff[r + 1] -= x; // 修改 [r+1,n] -x
}
for (int i = 1; i <= n; ++i) map[i] = map[i - 1] + diff[i];
// 通过给修改后的 差分数组求 前缀和，还原修改后的数组map
for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + map[i];
// 再次求前缀和
int q;
cin >> q;
while (q--) { // q次询问
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << endl;
}
}二维前缀和
定义一个矩阵为二维数组 $a[i,j]$ ，定义二维前缀和数组 $prefix[i][j]$ 为从 $[1,1]$ 到 $[i,j]$ 对角线，所呈现的范围内的数字和。
首先通过下述方式存储前缀和数组：
$$
prefix[i,j]=\sum_{t_i=1}^i\sum_{t_j=1}^ia_{i,j}=P[i-1][j]+P[i][j-1]-P[i-1]P[j-1]+a[i][j]
$$
然后再运算出矩阵 $i,j$ 范围内的数字之和：
$$
ans=P[x_2][y_2]-P[x_2][y_1-1]-P[x_1-1][y_2]+P[x_1-1][y_1-1]
$$
const int N = 1e3 + 9;
int n, m, q;
ll map[N][N], prefix[N][N];
// https://oj.eriktse.com/problem.php?id=1060
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> map[i][j]; // 将矩阵存储到二维数组
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
// 存储二维前缀和数组
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + map[i][j];
}
}
while (q--) { // q次询问
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1] << endl;
}
}二维差分
- 无需计算出差分数组，都将其默认为0
- 待补充
const int N = 1e3 + 9;
int n, m, q, map[N][N], diff[N][N];
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> map[i][j]; // 二维数组存一下
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
diff[i][j] += map[i][j];
diff[i][j + 1] -= map[i][j];
diff[i + 1][j] -= map[i][j];
diff[i + 1][j + 1] += map[i][j];
}
}
while (q--) { // q次添加操作
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
diff[x1][y1] += c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y1] -= c;
diff[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
map[i][j] = map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1] + diff[i][j];
cout << map[i][j] << " ";
}
cout << endl;
}
}附：例题贪心求最长子段和
开始学算法了熬，昕明
orz
Orz