前缀和And差分

 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

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n, m;
    cin >> n >> m;
    vector<i64> nums(n + 1, 0);
    vector<i64> sum(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        cin >> nums[i];
        sum[i] = sum[i - 1] + nums[i];
    }
    while(m--){
        i64 l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l - 1]  << '\n';
    }
}

int main()
{
    solve();
    return 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

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n, m, q;
    cin >> n >> m >> q;
    vector<vector<i64>> nums(n + 1, vector<i64>(m + 1, 0));
    vector<vector<i64>> sum(n + 1, vector<i64>(m + 1, 0));
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> nums[i][j];
            if(i = 0) sum[0][j] = sum[0][j - 1] + nums[0][j];
            if(j = 0) sum[i][0] = sum[i - 1][0] + nums[i][0];
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + nums[i][j];
        }
    }
    
    while(q--) {
        i64 x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        i64 ans = 0;
        if(!x1 && !y1 ) ans =  sum[x2][y2];  // 这一步与下面两步是在坐标从零开始的状态下
        if(!x1) ans = sum[x2][y2] - sum[x2][y1 - 1];  
        if(!y1) ans = sum[x2][y2] - sum[x1 - 1][y2];
        else ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
        cout << ans << endl; 
    }
    
}

int main() 
{
    solve();
    return 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

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n, m, q;
    cin >> n >> m >> q;
    vector<vector<i64>> nums(n + 1, vector<i64>(m + 1, 0));
    vector<vector<i64>> sum(n + 1, vector<i64>(m + 1, 0));
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> nums[i][j];
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + nums[i][j];
        }
    }
    
    while(q--) {
        i64 a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1] << "\n"; 
    }
    
}

int main() 
{
    solve();
    return 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

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m ,q;
    cin >> n >> m >> q;
    
    vector<vector<int>> nums(n + 2, vector<int>(m + 2, 0));
    vector<vector<int>> dif(n + 2, vector<int>(m + 2, 0));
    vector<vector<int>> ans(n + 2, vector<int>(m + 2, 0));

    auto insert = [&](int x1, int y1, int x2, int y2, int val) {
        dif[x1][y1] += val;
        dif[x2+1][y1] -= val;
        dif[x1][y2+1] -= val;
        dif[x2+1][y2+1] += val;
    };
    

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> nums[i][j];
            insert(i, j, i, j, nums[i][j]);
        }
    }
    
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= m; j++) {
    //         cout << dif[i][j] << " \n"[j == m]; 
    //     }
    // }

    while(q--) {
        int a, b, c, d, val;
        cin >> a >> b >> c >> d >> val;
        insert(a, b, c, d, val);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + dif[i][j];
            // dif[i][j] += dif[i - 1][j] + dif[i][j - 1] - dif[i - 1][j - 1];
            cout << ans[i][j] << " \n"[j == m];
        }
    }

}

int main()
{
    solve();
    return 0;
}