Forest density

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> pref(n + 1, vector<int>(n + 1, 0));

    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= n; x++) {
            char ch;
            cin >> ch;
            int tree = (ch == '*') ? 1 : 0;
            pref[y][x] = pref[y - 1][x] + pref[y][x - 1] - pref[y - 1][x - 1] + tree;
            //total-the non-included recs
            //from (1,1)
        }
    }

    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        int ans = pref[y2][x2] - pref[y1 - 1][x2] - pref[y2][x1 - 1] + pref[y1 - 1][x1 - 1];
        cout << ans << "\n";
    }
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED