前缀和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; } 一维差分 推导过程 ...