[BOJ] 11658 구간 합 구하기 3

1. 문제요약

11658번: 구간 합 구하기 3 (acmicpc.net)

11658번: 구간 합 구하기 3

 

N×N 크기의 표에 숫자들이 채워져 있다. 수의 변경이 빈번히 일어나고 연속 구간에 대한 부분합을 구하려고 한다.

 

2. 문제예제

 

3. 팩트추출

Fact 1 : 비슷한 문제인 10999번: 구간 합 구하기 2 (acmicpc.net) 와 다른 부분은 2차원 배열에서 수정 및 조회하며 구간 업데이트가 아니라 한 곳만 업데이트한다는 점이다. 연속된 공간의 연산이므로 세그먼트 트리와 펜윅 트리 모두 가능하다. 펜윅 트리에 대한 자세한 내용은 아래 블로그 글을 참고한다.

펜윅 트리 (바이너리 인덱스 트리) (acmicpc.net)

 

Fact 2 : 펜윅 트리를 2차원 배열에 적용하면 행과 열 모두 값이 업데이트된다. 맵 전체에 그 해당 인덱스가 필요하는 구간들이 업데이트된다. 예를 들어 map[0][0] 에 해당하는 부분이 펜윅 트리 맵에 저장될 때 다음과 같다.

(인덱스 바운드 예외를 처리하기 위해 용량을 하나씩 증가시켰다.)

map[0][0] 이 펜윅트리 tree[x][y] 에 저장될 때의 모습이다. 0 번째 인덱스이기 때문에 0번, 1번, 3번 인덱스 구간합에 모두 저장되는 것을 볼 수 있다.

 

4. 문제풀이(수동)

문제 예제 입력 1번 map 을 펜윅 트리(tree)에 저장하면 아래와 같다.

 

여기서 만약 (2, 2) 부터 (3, 4) 까지 구간합을 구하고 싶다면 아래 공식과 같이 전체 사각형에서 변두리 사각형 부분들을 빼주면 된다. 이 때 중복으로 제거한 부분을 다시 한 번 더해주어야 한다.

 

sum(3, 4) - sum(3, 2-1) - sum(2-1, 4) + sum(2-1, 2-1)

= 27

 

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 펜윅 트리방식으로 문제를 풀었다.

 

6. 소스코드

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

public class Main {
    static int N, M;
    static int[][] inputArray;
    static int[][] fenwickTree;

    private static void update(int x, int y, int val) {
        while(x <= N){
            int yIndex = y;
            while(yIndex <= N) {
                fenwickTree[x][yIndex] += val;
                yIndex += yIndex & -yIndex;
            }
            x += x & -x;
        }
    }

    private static int sum(int x, int y) {
        int result = 0;
        while(x > 0){
            int yIndex = y;
            while(yIndex > 0) {
                result += fenwickTree[x][yIndex];
                yIndex -= yIndex & -yIndex;
            }
            x -= x & -x;
        }
        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        inputArray = new int[N+1][N+1];
        fenwickTree = new int[N+1][N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                inputArray[i][j] = Integer.parseInt(st.nextToken());
                update(i, j, inputArray[i][j]);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            if(operation == 1) {
                int x2 = Integer.parseInt(st.nextToken());
                int y2 = Integer.parseInt(st.nextToken());
                sb.append((sum(x2, y2) - sum(x2, y1-1) - sum(x1-1, y2) + sum(x1-1,y1-1))+"\n");
            }else {
                int change = Integer.parseInt(st.nextToken());
                update(x1, y1, change - inputArray[x1][y1]);
                inputArray[x1][y1] = change;
            }
        }
        System.out.println(sb.toString());
    }
}