https://www.acmicpc.net/problem/2167

주어진 매 쿼리에 대해 배열의 합을 이중 for문을 돌면서 직접 원소 하나하나를 더해 계산하면 최악의 경우 시간복잡도는 O(KNM)이어서 제한시간을 넘길 가능성이 큽니다. 그렇기 때문에

D[i][j] : (1,1)부터 (i, j)까지를 더한 합을 미리 O(NM)에 채우고

i, j, x, y로 들어오는 쿼리에 대해 D[x][y] - D[x][j - 1] - D[i - 1][y] + D[i - 1][j - 1]를 계산하면 O(K)로 해결할 수 있습니다. 인덱싱을 0부터 할 수도 있고 1부터 할 수도 있는데 1로 하면 예외처리를 별로 안해줘도 돼서 편합니다.

https://github.com/encrypted-def/BOJ/blob/master/2193.cpp