前缀和 - Prefix Sum

Posted on Edited on In , Word count in article: 1.6k Reading time ≈ 6 mins.

补点基本算法

  • 一维前缀和
  • 二维前缀和

一维前缀和

原理

在反复计算区间内元素和时，通过前缀和可以实现 的效率

考虑一长度为 的数组
其中，区间 内的元素和为

由此我们可以通过 和 内元素和来计算区间 内的元素和
而要计算 中每个区间的元素和，我们仅需 的循环遍历即可，而这些区间的元素和，即为前缀和，记为 则

其中 , 使 从 遍历到 即可获得所有前缀和

例题

可获取的最小取值 lanqiaoOJ 3142

问题描述

有一个长度为 的数组 ，进行 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一：

  1. 取出数组中的最大元素
  2. 取出数组中的最小元素和次小元素
    要求在进行完 次操作后取出的数的和最小。

输入

第一行输入两个整数 和 ，表示数组长度和操作次数。
第二行输入 个整数，表示数组 。

数据范围

输出

输出一个整数，表示最小数的和。

示例

输入样例
1
2
5 1
2 5 1 10 6
输出样例
1
3

分析

因为有关最大最小，以及次小，我们需要先对 数组进行排序，再进行两种操作。

要注意的是，这里使用贪心算法，每次取操作 1 和操作 2 中的最小值并不可行。

例如 , 我们取 ， 那么如果按贪心算法,那我们每次都是做操作 2，结果是 ，而正确答案是做 次操作 1，结果是 。

因此其中一种解决方案是尝试所有组合， 我们记操作 2 做 次，则 操作 1 做 次，因为操作 1 是取最小和次小，我们可以等效为取两次最小（不放回），且数组从小到大排序

而这两个求和容易改写成前缀和，其中第一项已经是 的前缀和

实现

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
ll a[(int)1e5 * 2 + 10], s[(int)1e5 * 2 + 10];
void solve() {
  int n, k;
  ll ans = 1e18;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  sort(a, a + n + 1);
  for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
  for (int p = 0; p <= k; ++p) ans = min(s[2 * p] + s[n] - s[n + p - k], ans);
  cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

二维前缀和

原理

对于一个矩阵 ，类似的，我们可以求一个分块矩阵内的所有元素和，主对角线端点分别为 和 ， 那么我们有

类似的，可以写出二维前缀和，记 ，那么有

这里的 需要被减去是因为 和 都包含了这一部分。

例题

领地选择 洛谷 P2004

  • 领地选择

题目描述

作为在虚拟世界里统帅千军万马的领袖，小 Z 认为天时、地利、人和三者是缺一不可的，所以，谨慎地选择首都的位置对于小 Z 来说是非常重要的。

首都被认为是一个占地 的正方形。小 Z 希望你寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入格式

第一行三个整数 ，表示地图的宽和长以及首都的边长。

接下来 行每行 个整数，表示了地图上每个地块的价值。价值可能为负数。

输出格式

一行两个整数 ，表示首都左上角的坐标。

样例 #1

样例输入 #1
1
2
3
4
3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1
样例输出 #1
1
1 2

提示

对于 的数据，。
对于 的数据，。
对于 的数据，，。

分析

在 的矩阵中找一个内部和最大的 子矩阵
在此即可应用二维前缀和计算每一个 子矩阵的元素和

实现

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
#include <bits/stdc++.h>
#define mod (int)(1e9 + 7)
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
ll a[1010][1010], s[1010][1010];
void solve() {
  int n, m, c;
  cin >> n >> m >> c;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
      s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
    }
  int ans = -1e18, sum;
  int x = -1, y = -1;
  for (int i = 1; i <= n - c + 1; ++i) {
    for (int j = 1; j <= m - c + 1; ++j) {
      int rx = i + c - 1, ry = j + c - 1;
      // 加上 s[rx - c][ry - c] 是因为两块区域重复了
      sum = s[rx][ry] - s[rx - c][ry] + s[rx - c][ry - c] - s[rx][ry - c]; 
      if (sum > ans) {
        ans = sum;
        x = i;
        y = j;
      }
    }
  }
  cout << x << " " << y << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}