Forest density

#include <iostream>
#include <vector>
using namespace std;
 
int findTrees(int a, int b, int c, int d, vector<vector<int>>& segment) {
    return segment[c][d] - (b > 0 ? segment[c][b-1] : 0) - (a > 0 ? segment[a-1][d] : 0) 
           + (a > 0 && b > 0 ? segment[a-1][b-1] : 0);
}
 
void updateSegment(vector<vector<int>>& segment, vector<vector<char>>& forest) {
    int n = segment.size();
 
    segment[0][0] = (forest[0][0] == '*') ? 1 : 0;
 
    for (int i = 1; i < n; i++) {
        segment[i][0] = segment[i-1][0] + (forest[i][0] == '*' ? 1 : 0);
        segment[0][i] = segment[0][i-1] + (forest[0][i] == '*' ? 1 : 0);
    }
 
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            segment[i][j] = segment[i-1][j] + segment[i][j-1] - segment[i-1][j-1]
                            + (forest[i][j] == '*' ? 1 : 0);
        }
    }
}
 
int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<char>> forest(n, vector<char>(n));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> forest[i][j];
        }
    }
 
    vector<vector<int>> segment(n, vector<int>(n, 0));
    updateSegment(segment, forest);
    
    vector<vector<int>> queries(q, vector<int>(4));
    for (int i = 0; i < q; i++){
        for (int j = 0; j < 4; j++){
            cin >> queries[i][j];
        }
    }
    
    for (int i = 0; i < q; i++) {
        int sol = findTrees(queries[i][0]-1, queries[i][1]-1, queries[i][2]-1, queries[i][3]-1, segment);
        cout << sol << endl;
    }
 
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED