[9. submatrix sum]

Submatrix and （ Two dimensional prefixes and ）

Ideas ：

Calculate the sum of submatrix , For example （x1,y1） It's the upper left corner ,（x2,y2） Is the sum of the submatrix in the upper right corner .

Two problems need to be solved

1. s [ i , j ] How to calculate
   Line by line calculation

S[i,j] = S[i-1,j] + S[i,j-1] - S[i-1,j-1] + a[i,j]

2. With (x1,y1) It's the upper left corner ,(x2,y2) How to calculate the sum of all the numbers in the submatrix in the lower right corner

S[x2,y2] -S[x1-1,y2]-S[s2,y1-1]+S[x1-1,y1-1]

subject

Enter a n That's ok mm The integer matrix of columns , Input again q A asked , Each query contains four integers x1,y1,x2,y2 Represents the upper left and lower right coordinates of a submatrix .

For each query, the sum of all numbers in the output submatrix .

Input format

The first line contains three integers n,m,q

Next n That's ok , Each row contains m It's an integer , Represents an integer matrix .

Next q That's ok , Each line contains four integers x1,y1,x2,y2 A group of questions .

Output format

common q That's ok , Output one query result per line .

Data range

1 ≤ n ,m ≤ 1000
1 ≤ q ≤ 200000
1≤ x1 ≤ x2 ≤ n
1 ≤ y1 ≤ y2 ≤ m
−1000 ≤ The values of the elements in the matrix ≤ 1000

sample input ：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

sample output ：

17
27
21

Code

#include <iostream>
using namespace std;
const int N = 1010;

int n, m, q;
int a[N][N],s[N][N];

int main()
{
     
   scanf("%d%d%d",&n ,&m, &q);
   for (int i = 1; i <= n; i ++)    // Assign value to array 
       for (int j = 1; j <= m; j ++)
           scanf("%d",&a[i][j]);        
           
   // Initialize prefix and array 
   for (int i = 1; i <= n; i ++)
       for (int j = 1; j <= m; j ++)
           s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
           
   // Output prefix and 
   while (q --)
   {
     
       int x1,y1,x2,y2;
       scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
       printf("%d\n",s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
   }
   return 0;
}