peltorator

Prefix Sums 2D recurrent

Mar 8th, 2021
895
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<vector<int>> findPrefixSums2D(vector<vector<int>>& a) {
  6.     int n = a.size();
  7.     int m = a[0].size();
  8.     vector<vector<int>> prefixSum(n + 1, vector<int>(m + 1, 0));
  9.     for (int i = 0; i < n; i++) {
  10.         for (int j = 0; j < m; j++) {
  11.             prefixSum[i + 1][j + 1] = prefixSum[i][j + 1]
  12.                 + prefixSum[i + 1][j] - prefixSum[i][j] + a[i][j];
  13.         }
  14.     }
  15.     return prefixSum;
  16. }
  17.  
  18. int main() {
  19.     int n, m;
  20.     cin >> n >> m;
  21.     vector<vector<int>> arr(n, vector<int>(m, 0));
  22.     for (int i = 0; i < n; i++) {
  23.         for (int j = 0; j < m; j++) {
  24.             cin >> arr[i][j];prefix
  25.         }
  26.     }
  27.     vector<vector<int>> prefixSums = findPrefixSums2D(arr);
  28.     int queriesNumber;
  29.     cin >> queriesNumber;
  30.     for (int i = 0; i < queriesNumber; i++) {
  31.         int lx, ly, rx, ry;
  32.         cin >> lx >> ly >> rx >> ry;
  33.         lx--;
  34.         ly--;
  35.         cout << prefixSums[rx][ry] - prefixSums[lx][ry] - prefixSums[rx][ly] + prefixSums[lx][ly] << '\n';
  36.     }
  37. }
  38.  
RAW Paste Data