Forest density

#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct SegmentTree{
  std::vector<int> tree;
  int size;
  SegmentTree(std::vector<int>& arr){
    size = arr.size();
    tree.resize(4*size);
    buildTree(0, 0, size-1, arr);
  }

  void buildTree(int treeIndex, int rangeL, int rangeR, std::vector<int>& arr){
    if (rangeL==rangeR){
      tree[treeIndex] = arr[rangeL];
      return;
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);
    buildTree(treeLeftIdx, rangeL, mid, arr);
    buildTree(treeRightIdx, mid+1, rangeR, arr);

    tree[treeIndex] = tree[treeLeftIdx]+tree[treeRightIdx];
  }

  int getLeft(int idx){
    return 2*idx+1;
  }

  int getRight(int idx){
    return 2*idx+2;
  }

  int query(int treeIndex, int ql, int qr, int rangeL, int rangeR){
    if (ql <= rangeL && qr >= rangeR){
      return tree[treeIndex];
    }

    int mid = rangeL + (rangeR - rangeL)/2;
    int treeLeftIdx = getLeft(treeIndex);
    int treeRightIdx = getRight(treeIndex);

    int sum = 0;

    if (ql<=mid){
      sum+= query(treeLeftIdx, ql, qr, rangeL, mid);
    }
    if (qr>mid){
      sum+= query(treeRightIdx, ql, qr, mid+1, rangeR);
    }

    return sum;
  }
};


struct Rect{
  int y1, x1, y2, x2;
};


int main(){
  int tn, m;
  std::cin >> tn >> m;
  int n = tn*tn;
  std::vector<int> vals(n);
  for (int i = 0; i<tn; ++i){
    std::string row;
    std::cin >> row;
    for (int j = 0; j<tn; ++j){
      const char c = row[j];
      const char* t = "*"; 
      int tree = c==*t; //1 if tree, 0 if empty
      vals[i*tn+j] = tree;
    }
  }
  SegmentTree st(vals); //number of trees per row segment
  
  std::vector<Rect> queries(m);
  for (int q = 0; q<m; ++q){
    int y1,x1,y2,x2;
    std::cin >> y1 >> x1 >> y2 >> x2;
    queries[q].y1 = y1-1;
    queries[q].x1 = x1-1;
    queries[q].y2 = y2-1;
    queries[q].x2 = x2-1;
  }

  for (int q = 0; q<m; ++q){
    int sum = 0;
    for (int row = queries[q].y1; row<=queries[q].y2; row++){
      int rowStride = row*tn;
      sum += st.query(0, rowStride+ queries[q].x1, rowStride+queries[q].x2, 0, st.size-1);
    }
    std::cout << sum << "\n";
  }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED