Forest density

def print2d(ma):
    for line in ma:
        for ch in line:
            print(ch, end=" ")
        print()

size, queryCount = [int(aa) for aa in input().strip().split(" ")]
trees = set()
sumMap = [[0 for _ in range(size)] for _ in range(size)]
for yy in range(size):
    for xx, ee in enumerate(input()):
        if ee == "*":
            trees.add((xx,yy))

sumMap[0][0] = 1 if (0,0) in trees else 0
for xx in range(1, size):
    sumMap[0][xx] = sumMap[0][xx-1] + (1 if (xx,0) in trees else 0)
for yy in range(1, size):
    sumMap[yy][0] = sumMap[yy-1][0] + (1 if (0,yy) in trees else 0)
    for xx in range(1, size):
        sumMap[yy][xx] = (
            sumMap[yy-1][xx] 
            + sumMap[yy][xx-1] - sumMap[yy-1][xx-1] + (1 if (xx,yy) in trees else 0)
            )

def getSubSum(startY,startX,endY,endX):
    # print(sumMap[endY][endX],endX,endY)
    # print(sumMap[startY][startX],startX,startY)
    ret = sumMap[endY][endX]
    if startY != 0:
        ret -= sumMap[startY-1][endX]
    if startX != 0:
        ret -= sumMap[endY][startX-1]
    if startY != 0 and startX != 0:
        ret += sumMap[startY-1][startX-1]
    return ret

for ii in range(queryCount):
    query = [int(aa)-1 for aa in input().strip().split(" ")]
    # if ii != 1:
    #     continue
    ret = getSubSum(*query)
    print(ret)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED