Forest density

#include <iostream>
#include <vector>

using namespace std;


void preProcess(const vector<vector<int>>& mat, vector<vector<int>>& aux) 
{ 
    int N = mat[0].size();
    int M = mat.size();

    for (int i=0; i<N; i++) aux[0][i] = mat[0][i]; 
  
    for (int i=1; i<M; i++){ 
      for (int j=0; j<N; j++){
         aux[i][j] = mat[i][j] + aux[i-1][j]; 
        }
    }
  
   for (int i=0; i<M; i++) 
      for (int j=1; j<N; j++) 
         aux[i][j] += aux[i][j-1]; 
} 

int sumQuery(const vector<vector<int>>& aux, int tli, int tlj, int rbi,  int rbj) 
{ 
    int res = aux[rbi][rbj]; 
  
    if (tli > 0) 
       res = res - aux[tli-1][rbj]; 
  
    if (tlj > 0) 
       res = res - aux[rbi][tlj-1]; 

    if (tli > 0 && tlj > 0) 
       res = res + aux[tli-1][tlj-1]; 
  
    return res; 
} 

int main(){
    int n,q;
    cin >> n >> q;
    vector<vector<int>> mat(n, vector<int>(n));
    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            char p;
            cin >> p;
            if(p=='.'){
                mat[i][l] = 0;
            }
            else mat[i][l] = 1;
        }
    }
    vector<vector<int>> aux(n, vector<int>(n));

    preProcess(mat, aux);

    for(int i=0; i<q; i++){
        int y1,x1,y2,x2;
        cin >> y1 >> x1 >> y2 >> x2;
        cout << sumQuery(aux,y1-1,x1-1,y2-1,x2-1) <<endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED