前缀和
前缀和（Prefix Sum）是一个非常常见且高效的算法技巧，用来快速计算数组或矩阵中某个区间的元素和。它的核心思想是通过预处理数组（或矩阵），构建一个新的数组（或矩阵），使得可以在常数时间内计算任意区间的和，从而显著提高效率。
原理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
using namespace std;
using ll = long long;
const ll N = 1e5 + 9;
ll arr[N] = {0};
ll prefix[N] = {0};
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
prefix[i] = prefix[i - 1] + arr[i];
}
int m;
cin >> m;
while (m--) {
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << endl;
}
return 0;
}
|
二维前缀和
目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是O(1)的操作
1 根据原始状况，生成二维前缀和数组sum，
sum[i][j]: 代表左上角(0,0)到右下角(i,j)这个范围的累加和
sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
2 查询左上角(a,b)到右下角(c,d)这个范围的累加和
sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
3 实际过程中往往补第0行、第0列来减少很多条件判断。
当然也可以不补。根据个人习惯决定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include <cstdio>
using namespace std;
using ll = long long;
const ll N = 1e3;
ll arr[N][N] = {0};
ll prefix[N][N] = {0};
int main()
{
int n;
cin >> n;
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + arr[i][j];
}
}
cout << "原数组:" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%4lld ", arr[i][j]);
}
cout << endl;
}
cout << "二维前缀和:" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%4lld ", prefix[i][j]);
}
cout << endl;
}
ll submatrix_sum = prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];
cout << "查询区域: (" << x1 << ", " << y1 << ") 到 (" << x2 << ", " << y2 << ")" << endl;
cout << "子矩阵的和: " << submatrix_sum << endl;
return 0;
}
|
差分
差分（Difference）是一种常见的算法技巧，通常用于处理数组或区间更新问题。差分的基本思想是通过对数组的差分（即存储相邻元素的差值）来高效地进行区间修改或区间查询。
原理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
using namespace std;
using ll = long long;
const ll N = 1e5 + 9;
ll arr[N] = {0};
ll diff[N] = {0};
ll prefix[N] = {0};
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
diff[i] = arr[i] - arr[i - 1];
}
cout << "差分数组:\n";
for (int i = 1; i <= n; i++) {
cout << diff[i] << " ";
}
cout << endl;
int l, r;
cin >> l >> r;
diff[l] += 1;
diff[r + 1] -= 1;
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + diff[i];
}
cout << "还原后的数组:\n";
for (int i = 1; i <= n; i++) {
cout << prefix[i] << " ";
}
cout << endl;
return 0;
}
|
二维差分
在二维数组中，如果经历如下的过程
1 批量的做如下的操作，每个操作都有独立的a、b、c、d、v
void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？
2 操作做完后，如何正确得到二维数组中每个位置的值？
这就是二维差分的主要工作，add时候快速处理，最后build得到每个位置的值，修改操作必须集中在一起，不能边修改边查询。
1）add方法实现，比较巧妙！
2）build方法实现，和处理前缀和类似
3）真实数据用一圈0包裹起来，可以减少很多边界讨论
1
2
3
4
5
6
7
| void build() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
}
}
}
|
1
2
3
4
5
6
| void add(int a, int b, int c, int d, int v) {
diff[a][b] += v;
diff[c + 1][b] -= v;
diff[a][d + 1] -= v;
diff[c + 1][d + 1] += v;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
using namespace std;
using ll = long long;
ll arr[1009][1009] = {0};
ll diff[1009][1009] = {0};
ll sum[1009][1009] = {0};
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
diff[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];
}
}
while (q--) {
int x1, y1, x2, y2, k;
cin >> x1 >> y1 >> x2 >> y2 >> k;
diff[x1][y1] += k;
diff[x1][y2 + 1] -= k;
diff[x2 + 1][y1] -= k;
diff[x2 + 1][y2 + 1] += k;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + diff[i][j];
cout << sum[i][j] << " ";
}
cout << endl;
}
return 0;
}
|
https://www.luogu.com.cn/problem/P7404
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <bits/stdc++.h>
#define int long long
using namespace std;
int n, cnt;
const int N = 2e5 + 10;
int arr[N];
int diff[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
diff[i] = arr[i] - arr[i - 1];
}
int l = 1, r = n;
while (l < r) {
while (diff[l] > 0) {
l++;
}
while (diff[r] < 0) {
r--;
}
if (l > r) {
break;
}
int x = min(abs(diff[l]), diff[r]) + 1;
diff[l] += x;
diff[r] -= x;
cnt += x;
}
cout << cnt << endl;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
|