peltorator

Prefix Sums 2D from 1D

Mar 8th, 2021 (edited)
459
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> findPrefixSums(vector<int>& a) {
  6.     int n = a.size();
  7.     vector<int> prefixSums(n + 1, 0);
  8.     for (int i = 0; i < n; i++) {
  9.         prefixSums[i + 1] = prefixSums[i] + a[i];
  10.     }
  11.     return prefixSums;
  12. }
  13.  
  14. vector<vector<int>> findPrefixSums2D(vector<vector<int>>& a) {
  15.     int n = a.size();
  16.     int m = a[0].size();
  17.     vector<vector<int>> prefixSum1D(n);
  18.     for (int i = 0; i < n; i++) {
  19.         prefixSum1D[i] = findPrefixSums(a[i]);
  20.     }
  21.     vector<vector<int>> prefixSum2D(n + 1, vector<int>(m + 1, 0));
  22.     for (int j = 0; j <= m; j++) {
  23.         for (int i = 0; i < n; i++) {
  24.             prefixSum2D[i + 1][j] = prefixSum2D[i][j] + prefixSum1D[i][j];
  25.         }
  26.     }
  27.     return prefixSum2D;
  28. }
  29.  
  30. int main() {
  31.     int n, m;
  32.     cin >> n >> m;
  33.     vector<vector<int>> arr(n, vector<int>(m, 0));
  34.     for (int i = 0; i < n; i++) {
  35.         for (int j = 0; j < m; j++) {
  36.             cin >> arr[i][j];
  37.         }
  38.     }
  39.     vector<vector<int>> prefixSums = findPrefixSums2D(arr);
  40.     int queriesNumber;
  41.     cin >> queriesNumber;
  42.     for (int i = 0; i < queriesNumber; i++) {
  43.         int lx, ly, rx, ry;
  44.         cin >> lx >> ly >> rx >> ry;
  45.         lx--;
  46.         ly--;
  47.         cout << prefixSums[rx][ry] - prefixSums[lx][ry] - prefixSums[rx][ly] + prefixSums[lx][ly] << '\n';
  48.     }
  49. }
  50.  
RAW Paste Data