Forest density

#include <bits/stdc++.h>

using namespace std;

int n;

int tree_min(vector<int> &tree, int a, int b) {
  a += n;
  b += n;
  int m = 0;

  while (a <= b) {
    if ((a % 2) == 1) {
      m ^= tree[a];
      a++;
    }
    if ((b % 2) == 0) {
      m ^= tree[b];
      b--;
    }
    a /= 2;
    b /= 2;
  }
  return m;
}

void update(vector<int> &tree, int i, int v) {
  i += n;
  tree[i] = v;
  int newMin;
  while (i > 1) {
    i /= 2;
    newMin = tree[2 * i] ^ tree[2 * i + 1];
    if (tree[i] != newMin) {
      tree[i] = newMin;
    } else
      return;
  }
}

int main() {
  // ios::sync_with_stdio(false);
  // cin.tie(0);
  int q;
  cin >> n >> q;

  auto values = vector<string>(n, "");

  auto sumarr = vector<vector<int>>(n, vector<int>(n));

  for (int i = 0; i < n; i++) {
    cin >> values[i];
  }

  for (int i = 0; i < n; i++) {
    for (int y = 0; y < n; y++) {
      int c = 0;

      for (int x = 0; x <= i; x++) {
        for (int yy = 0; yy <= y; yy++) {
          if (values[x][yy] == '*') c++;
        }
      }
      sumarr[i][y] = c;
    }
  }

  for (int i = 0; i < q; i++) {
    int y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    y1--;
    x1--;
    y2--;
    x2--;
    int A = sumarr[y2][x2];
    if (x1 > 0) A -= sumarr[y2][x1 - 1];
    if (y1 > 0) A -= sumarr[y1 - 1][x2];
    if (y1 > 0 && x1 > 0) A -= sumarr[y1 - 1][x1 - 1];

    cout << A << endl;
  }

  return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED