Forest density

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> preprocess_forest(vector<vector<char> >& grid, int n)
{
    vector<vector<int> > prefix(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int value = 0;
            if(grid[i - 1][j - 1] == '*') value = 1;
            prefix[i][j] = value + prefix[i - 1][j]
                           + prefix[i][j - 1]
                           - prefix[i - 1][j - 1];
        }
    }
    return prefix;
}

int count_trees_in_rectangle(vector<vector<int> >& prefix,
                             int x1, int y1, int x2, int y2)
{
    return prefix[x2][y2] - prefix[x1 - 1][y2]
           - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];
}

int main()
{
    int n,q;
    cin >> n >>q;
    vector<vector<char> > grid(n,vector<char>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j)
            cin>>grid[i][j];
    }
    vector<vector<int> > prefix
        = preprocess_forest(grid, n);
    for (int i = 0; i < q; i++) {
      	int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << count_trees_in_rectangle(prefix, x1, y1, x2,y2) << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED