[11660] 구간 합 구하기 5

// 11660 구간 합 구하기 5 
// 펜윅과 다른 점 -> 업데이트가 없다  
#include<iostream>
#include<cstdio>
#include<string.h>
#define MAX 1025
using namespace std;

int arr[MAX][MAX];
int dp[MAX][MAX];
int N, M, x1, y1, x2, y2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	memset(arr, 0, sizeof(arr));
	memset(dp, 0, sizeof(dp));
	
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++){ // 수 입력   
    	for(int j=1; j<=N; j++){
    		scanf("%d", &arr[i][j]);
		}
	}
	
	for(int i=1; i<=N; i++){ // 누적합  
		for(int j=1; j<=N; j++){
			dp[i][j] = arr[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
		}

	}
	// 누적합 확인  
//	for(int i=1; i<=N; i++){
//		for(int j=1; j <=N; j++){
//			printf("%d ", dp[i][j]);	
//		}
//		printf("\n");
//	}	
//	
	for(int i=1; i<=M; i++){
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		int ans = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
		printf("%d\n", ans); 
	}
	
	return 0;
}