Forest density

def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines()

    n, q = map(int, data[0].split())
    grid = data[1:n+1]
    
    # Create a prefix sum array
    prefix = [[0] * (n + 1) for _ in range(n + 1)]

    # Fill the prefix sum array
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            is_tree = 1 if grid[i - 1][j - 1] == '*' else 0
            prefix[i][j] = (is_tree + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1])

    results = []
    # Process each query
    for line in data[n + 1:n + 1 + q]:
        y1, x1, y2, x2 = map(int, line.split())
        count = (prefix[y2][x2] 
                  - prefix[y1 - 1][x2] 
                  - prefix[y2][x1 - 1] 
                  + prefix[y1 - 1][x1 - 1])
        results.append(str(count))

    # Print all results
    print("\n".join(results))

if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED