Problem - Forest Queries

Given an $n \times n$ grid with trees (*) and empty cells (.), answer queries: how many trees in rectangle $(r_1, c_1, r_2, c_2)$? This is 2D range sum on a static grid. Options:

$1.$ 2D prefix sums: $O(nm)$ build, $O(1)$ query

$2.$ 2D Sparse Table for sum: doesn't work (sum not idempotent) For counting, 2D prefix sums is the right choice. But if the query was "what's the maximum value in this rectangle?", 2D sparse table would apply. Constraints: $n$ up to $1000$, $q$ up to $2 \cdot 10^5$.