004 : 2차원 배열의 구간 합

> 2차원 행렬에 3차원 블럭(음양 / 값의 존재 여부) 만들기

 

일반 TP[](A[])와 합 S[]의 capacity는 같다

- 1부터 ~ 5까지

- 1까지 합 ~ 5까지의 합

 

두번 더하고 난 뒤 - 마이너스 보정 + 해당 포인트 박아넣기

 

 

 

 

 

전체에서 - 직전들을 두번 빼고 +  플러스 보정

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        // ISC
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());


        // D2F
        int[][] TP = new int[V+1][V+1];
        for (int i = 1; i <= V; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= V; j++) {
                TP[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // O1
        int[][] S = new int[V+1][V+1];
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + TP[i][j];
            }
        }

        // O2 + OEC patch
        for (int i = 0; i < M; 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 plate = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1];
            System.out.println(plate);
        }
    }
}