前缀和的基础讲解

youhualiuh / 2024-03-10 / 原文

什么是前缀和看题目要看范围被爆int你没话说需要养成习惯

O(N)的预处理 以O(1)的时间求部分和

S[1, N] = a1 + a2 + ... + aN;
我们如果要求S[L, R]
a1 + a2 + ... + aL-1 + aL + ... + aR
就是要aL + ... + aR的部分 -》 S[R] - S[L - 1]

S[]怎么来 S[i] = S[i - 1] + a[i]

前缀和的逆

它是前缀和的转变 a[i] = pre[i] - pre[i - 1]

Code:

#include <bits/stdc++.h>
    
using namespace std; 
const int N = 105;

int pre[N];

int main() { 
    int N; cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> pre[i];
    }
    for (int i = 1; i <= N; i++) {
        cout << pre[i] - pre[i - 1] << " \n"[i == N];
    }
    return 0;
}

Index * A

求出连续长度为M的子数组B的 i * Bi + M * Bm的最大值

类似高中的错位相减法
a1 + a2 + a3 + a4 + a5 +...
1-
a1 * 1 + a2 * 2 + a3 * 3 + a4 * 4
2-
a2 * 1 + a3 * 2 + a4 * 3 + a5 * 4

-> pre[4] - pre[0]
1得到2式子
cur - pre[4] - pre[0] + m * a[5]

以
4 2
5 4 -1 8 ans -> 15 这个为例子

我们先得到第一个
cur1 = 5 * 1 + 4 * 2 = 13

第二个
cur2 = 4 * 1 + -1 * 2 = 2

第三个
cur3 = -1 * 1 + 8 * 2 = 15

我们需要得到这样的结果 统计最大值

pre[] -》 前缀和
5 9 8 16

我们不乏可以发现
第一个是需要cur1 - 4得到 cur2 + 2 * a[2] ->
cur2 = 4 * 1 + -1 * 2

我们在拓展到m = 3的时候
5 3
5 4 -1 8 6  ans -> 33
pre[] -> 5 9 8 16 22

cur1 = 5 * 1 + 4 * 2 + -1 * 3 = 10

cur2 = 4 * 1 + -1 * 2 + 8 * 3 = 26

cur3 = -1 * 1 + 8 * 2 + 6 * 3 = 33

cur1 - 5 - 4 - 1 + 8 * 3这个值 得到 cur2

从这里你可以推出一个公式
-》
cur = cur - (pre[i + m - 1] - pre[i - 1]) + m * a[i]
最后取最大值就看了

Code:

#include <bits/stdc++.h>
    
using namespace std;
using i64 = long long; 
const int N = 2e5 + 5;

i64 a[N], pre[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); 
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    i64 ans = -1e18, cur = 0;
    for (int i = 1; i <= m; i++) {
        cur += a[i] * i;
    }
    for (int i = 1; i <= n - m + 1; i++) {
        ans = max(ans, cur);
        if (i != n - m + 1) {
            cur -= pre[i + m - 1] - pre[i - 1];
            cur += m * a[i + m];
        }
    }
    cout << ans;
    return 0;
}