2차원 배열 누적 합

2차원 배열 누적 합, 특정 구간 합 구하기

public class PrefixSum2D {
    public static void main(String[] args) {
        int[][] board = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        // 누적합 계산 (크기 N+1, M+1)
        int[][] sum = computePrefixSum(board);

        // 부분합 구하기: 예를 들어 (1,1)부터 (2,2)까지의 합
        int a = 1, b = 1, c = 2, d = 2;
        int result = getSubmatrixSum(sum, a, b, c, d);

        System.out.println("Submatrix Sum: " + result);
    }

    public static int[][] computePrefixSum(int[][] board) {
        int N = board.length;
        int M = board[0].length;

        // 누적합 배열 크기: N+1 x M+1
        int[][] sum = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                sum[i][j] = board[i - 1][j - 1]
                          + sum[i - 1][j]  // 위쪽 값
                          + sum[i][j - 1]  // 왼쪽 값
                          - sum[i - 1][j - 1]; // 겹치는 값 제거
            }
        }

        return sum;
    }

    public static int getSubmatrixSum(int[][] sum, int a, int b, int c, int d) {
        // (a, b)에서 (c, d)까지의 합
        return sum[c + 1][d + 1]
             - sum[a][d + 1]
             - sum[c + 1][b]
             + sum[a][b];
    }
}