def solve(grid, queries):
n = len(grid)
# Build 2D prefix sum
prefix = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
for j in range(n):
prefix[i+1][j+1] = (prefix[i][j+1] + prefix[i+1][j]
- prefix[i][j]
+ (1 if grid[i][j] == '*' else 0))
results = []
for r1, c1, r2, c2 in queries:
count = (prefix[r2][c2] - prefix[r1-1][c2]
- prefix[r2][c1-1] + prefix[r1-1][c1-1])
results.append(count)
return results
Time: . The inclusion-exclusion formula handles overlapping corners.