2차원 배열의 구간 합

세로줄 열, 위에서 아래로 내려오는 것이 x이다

배열 요소 먼저 넣기

// Line 2~
int A[][] = new int[N+1][N+1];
for (int x = 0; x <= N; x++) {
    st = new StringTokenizer(br.readLine());
    for (int y = 0; y <= N; y++) {
        A[x][y] = Integer.parseInt(st.nextToken());
    }
}

-

 

점화식으로 구간 합 구하기

// S 전처리
int S[][] = new int[N+1][N+1];
for (int x = 1; x <= N; x++) {
    for (int y = 1; y <= N; y++) {
        S[x][y] = S[x][y-1] + s[x-1][y] - S[x-1][y-1] + A[x][y];
    }
}

 

-

// L3~ + 비즈니스 로직 처리
for (int i = 0; i < Q; i++) {
    st = new StringTokenizer(br.readLine());
    int x1 = Integer.parseInt(st.nextToken());
    int y1 = Integer.parseInt(st.nextToken());
    int x2 = Integer.parseInt(st.nextToken());
    int y2 = Integer.parseInt(st.nextToken());
    int result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
    System.out.println(result);
}