[数据结构与算法]差分前缀和 题集&题解

题目来自洛谷题单【算法2-1】前缀和与差分

P5638 【CSGRound2】光骓者的荣耀

前缀和模板题

1. 对城市序列前缀和prefix[i]
2. 每次计算跳过[i,i+k)的时间

#include<bits/stdc++.h>
using namespace std;
int n, k;
vector<long long> a, prefix;
int main(){
    cin >> n >> k;
    a = vector<long long>(n, 0);
    prefix = vector<long long>(n, 0);
    prefix[0] = 0;
    for (int i = 1; i < n;i++){
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    long long ans = 0;
    for (int i = 0; i < n-k;i++){
        ans = max(ans, prefix[i+k] - prefix[i]);
    }
    cout << prefix[n-1] - ans;
    return 0;
}

P1115 最大子段和

前缀和模板题

1. prefix[i]记录i之前的前缀的和（可以用sum优化）
2. m记录前缀的最小值
3. 注意初值的设置。需要考虑到[0,i)序列的情况，所以m=0；ans是最终结果，ans=INT_MAX

#include<bits/stdc++.h>
using namespace std;
int main(){
    // freopen("../a.in", "r", stdin);
    // freopen("../a.out", "w", stdout);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0;i<n;i++)
        cin >> a[i];
    int sum = a[0];
    int m = 0, ans = INT_MIN;
    for (int i = 1; i < n;i++){
        sum += a[i];
        ans = max(ans, sum - m);
        m = min(m, sum);
    }
    cout << ans;
    return 0;
}

1719 最大加权矩形

二维前缀和模板题，且为最大子段和plus

1. 对a做前缀和prefix
2. 遍历每个(i,j)之前的下标，利用prefix计算区间和

#include<bits/stdc++.h>
using namespace std;
int main(){
    // freopen("../a.in", "r", stdin);
    // freopen("../a.out", "w", stdout);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            cin >> a[i][j];
        }
    }
    vector<vector<int>> prefix(n, vector<int>(n, 0));
    int ans = INT_MIN;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            if(i>0 && j>0)
                prefix[i][j] -= prefix[i - 1][j - 1];
            if(i>0)
                prefix[i][j] += prefix[i - 1][j];
            if(j>0)
                prefix[i][j] += prefix[i][j - 1];
            prefix[i][j] += a[i][j];
            ans = max(ans, a[i][j]);
            for (int ii = 0; ii <= i;ii++){
                for (int jj = 0; jj < j;jj++){
                    // (ii,jj) (i,j)
                    int m = prefix[i][j];
                    if(ii>0 && jj>0)
                        m += prefix[ii - 1][jj - 1];
                    if(ii>0)
                        m -= prefix[ii - 1][j];
                    if(jj>0)
                        m -= prefix[i][jj - 1];
                    ans = max(ans, m);
                }
            }
        }
    }
    cout << ans;
}

P3406 海底高铁

一维差分模板题
其实就是统计每段铁路经过的次数，也就是O(n)在区间上每个数加相同的数，考虑用差分

1. 对每段铁路经过的次数差分diff
2. 对diff求前缀和cnt就是最终次数
3. 每段铁路上贪心地选择省钱的方案
4. 注意long long

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    int pre, cur;
    // diff[i]: i->i+1
    vector<int> diff(n, 0);
    cin >> pre;
    for (int i = 1; i < m;i++){
        cin >> cur;
        diff[min(pre, cur) - 1]++;
        diff[max(pre, cur) - 1]--;
        pre = cur;
    }
    vector<int> a(n - 1), b(n - 1), c(n - 1);
    for (int i = 0; i < n - 1;i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    long long sum = diff[0];
    long long ans = min(sum * a[0], c[0] + sum * b[0]);
    for (int i = 1; i < n - 1;i++){
        sum = sum + diff[i];
        ans += min(sum * a[i], c[i] + sum * b[i]);
    }
    cout << ans;
    return 0;
}

P2004 领地选择

二维前缀和模板题

#include<bits/stdc++.h>
using namespace std;
int main(){
    // freopen("../a.in", "r", stdin);
    // freopen("../a.out", "w", stdout);
    int n, m, c;
    cin >> n >> m >> c;
    int cur;
    vector<vector<int>> prefix(n, vector<int>(m));
    int x = 0, y = 0, ans = INT_MIN;
    for (int i = 0; i < n;i++){
        for (int j = 0;j<m;j++){
            cin >> cur;
            prefix[i][j] = cur;
            if(i>0){
                prefix[i][j] += prefix[i - 1][j];
            }
            if(j>0){
                prefix[i][j] += prefix[i][j - 1];
            }
            if(i>0 && j>0){
                prefix[i][j] -= prefix[i - 1][j - 1];
            }
            if(i+1>=c && j+1>=c){
                int v = prefix[i][j];
                if(i>=c)
                    v -= prefix[i - c][j];
                if(j>=c)
                    v -= prefix[i][j - c];
                if(i>=c && j>=c)
                    v += prefix[i - c][j - c];
                if(v > ans){
                    x = i - c + 1;
                    y = j - c + 1;
                    ans = v;
                }
            }
        }
    }
    cout << x + 1 << " " << y + 1;
    return 0;
}

P3397 地毯

本题是二维差分/前缀和的模板题
差分用于维护区间上的各元素的同加、同减
差分初始化：
$$diff[x][y]=a[i][j]?a[i?1][j]?a[i][j?1]+a[i?1][j?1]$$
差分维护：
$$diff[x1][y1]+=x$$
$$diff[x2+1][y1]?=x$$
$$diff[x1][y2+1]?=x$$
$$diff[x2+1][y2+1]+=x$$
前缀和还原：
$$prefix[i][j]=diff[i][j]+prefix[i?1][j?1]+prefix[i?1][j]+preifx[i][j?1]$$

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m, n;
    cin >> n >> m;
    vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));
    int x1, y1, x2, y2;
    for (int i = 0; i < m;i++){
        cin >> x1 >> y1 >> x2 >> y2;
        diff[x1 - 1][y1 - 1]++;
        diff[x2][y1 - 1]--;
        diff[x1 - 1][y2]--;
        diff[x2][y2]++;
    }
    vector<vector<int>> prefix(n, vector<int>(n, 0));
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            if(i>0 && j>0)
                prefix[i][j] -= prefix[i - 1][j - 1];
            if(i>0)
                prefix[i][j] += prefix[i - 1][j];
            if(j>0)
                prefix[i][j] += prefix[i][j - 1];
            prefix[i][j] += diff[i][j];
            cout << prefix[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

P2671 [NOIP2015 普及组] 求和

从这题可以体会出，前缀和不局限在简单区间求和上，本质上是一种预处理的思想
把需要重复计算的数据计算出来离线使用

#include<bits/stdc++.h>
using namespace std;
const int MOD = 10007;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> num(n), color(n);
    for (int i = 0; i < n;i++)
        cin >> num[i];
    for (int i = 0; i < n;i++)
        cin >> color[i];
    unordered_map<int, vector<vector<int>>> umap;
    // O(N)
    for (int i = 0; i < n;i++){
        if(umap.find(color[i]) == umap.end()){
            umap[color[i]] = vector<vector<int>>(2);
        }
        if(i&1)
            umap[color[i]][1].push_back(i);
        else
            umap[color[i]][0].push_back(i);
    }
    // O(N)
    unordered_map<int, vector<int>> pre;
    for(const auto& vv: umap){
        int c = vv.first;
        const auto &nums = vv.second;
        pre[c] = vector<int>(2, 0);
        for (int k = 0; k < 2;k++){
            int size = nums[k].size();
            if(size < 2)
                continue;
            // part1
            int part1 = 0, tmp1 = 0;
            for (int i = 0; i < size;i++){
                int xi = nums[k][i];
                part1 = (part1 + ((xi + 1) % MOD) * (num[xi] % MOD) % MOD) % MOD;
                tmp1 = (tmp1 + num[xi]) % MOD;
            }
            part1 = part1 % MOD * (size - 2) % MOD;
            // part2
            int part2 = 0;
            for (int i = 0; i < size;i++){
                int xi = nums[k][i];
                part2 = (part2 + ((xi + 1) % MOD)) % MOD;
            }
            part2 = part2 * tmp1 % MOD;
            pre[c][k] = part1 + part2;
        }
    }
    // O(LEN(COLOR))
    int ans = 0;
    for(const auto& vv: pre){
        for (int k = 0; k < 2;k++){
            ans = (ans + pre[vv.first][k]) % MOD;
        }
    }
    cout << ans % MOD;
    return 0;
}