I tried to solve the forest queries problem but my solution kept exceeding time limit, and my solution was almost exactly the same as the example, I am not sure what is wrong, here is my solution:
Solution (python)
n, q = map(int, input().split())
forest = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
line = list(input())
for j in range(1, n + 1):
forest[i][j] = forest[i][j - 1] - forest[i - 1][j - 1] + forest[i - 1][j] + int(line[j - 1] == “*”)
for i in range(q):
y1, x1, y2, x2 = map(int, input().split())
print(forest[y2][x2] + forest[y1 - 1][x1 - 1] - forest[y2][x1 - 1] - forest[y1 - 1][x2])
