누적합(Cumulative sum) 2

2차원 누적합

누적합의 개념을 2차원으로 확장시킬 수 있다.

1차원 배열(arr)은 2차원으로 확장되고, 누적합 수열도 2차원 배열(sumArr) 형태로 확장된다.

직사각형 형태의 배열에 포함되는 직사각형 구간의 모든 원소의 합을 빠르게 구할 수 있다.

 

 

2차원 누적합 수열 만들기

 

a(i, j)에서 가로 방향으로 누적합을 계산해서 s(i, j) 수열이 되고, 계산한 결과를 세로 방향으로 누적합을 구해서 최종적인 S(i, j) 수열이 된다.

 

 

 

2차원 구간합 계산하기

 

S(i, j)는 위에서 설명한 방법대로 a(i, j) 배열의 누적합을 계산한 배열이다.

 

초록색으로 표시된 작은 사각형의 구간합을 구하기 위해서는 S(3, 3)에서 시작한다.

S(3, 3) 값에서 S(1, 3) 값과 S(3, 1) 값을 뺀 뒤에 S(1, 1) 값을 더해준다.

A, B집합의 합집합을 구할 때, 두 번 더한 가운데 부분을 빼주는 것과 같은 논리로 두 번 뺀 부분은 한번 더해줘야한다.

 

(x1, y1) 부터 (x2, y2) 까지의 값을 Range(a, b, c, d)라고 할 때 이를 수식으로 나타내면 다음과 같다.

Range(a, b, c, d) = S(x2, y2) - S(x1 - 1, y2) - S(x2, y1 - 1) + S(x1 -1, y1 -1)

 

 

[Codeforces] Star sky

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int T, n, q, c;
    static int[][][] arr, sumArr;
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        q = stoi(st.nextToken());
        c = stoi(st.nextToken());
 
        init();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a, b, c;
            a = stoi(st.nextToken());
            b = stoi(st.nextToken());
            c = stoi(st.nextToken());
            arr[a][b][c]++;
        }
 
        for (int s = 0; s < 11; s++) {
            for (int x = 0; x < 101; x++) {
                for (int y = 0; y < 100; y++) {
                    arr[x][y + 1][s] += arr[x][y][s];
                }
            }
        }
        for (int s = 0; s < 11; s++) {
            for (int x = 0; x < 101; x++) {
                for (int y = 0; y < 100; y++) {
                    arr[y + 1][x][s] += arr[y][x][s];
                }
            }
        }
 
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int t, x1, y1, x2, y2;
            t = stoi(st.nextToken());
            x1 = stoi(st.nextToken());
            y1 = stoi(st.nextToken());
            x2 = stoi(st.nextToken());
            y2 = stoi(st.nextToken());
            int sum = 0;
            for(int src = 0; src<11; src++) {
                int add = (src+t) % (c+1);
                int num = arr[x2][y2][src] - arr[x1-1][y2][src] - arr[x2][y1-1][src] + arr[x1-1][y1-1][src];
                sum += add*num;
            }
            System.out.println(sum);
        }
        
    }
 
    static void init() {
        arr = new int[101][101][11];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
 
    static void print(int[][][] a, int z) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j][z] + " ");
            }
            System.out.println();
        }
    }
}

 

복잡도 분석

누적합을 사용하는데에는 2단계의 step이 있다.

 

1. 전처리 : 누적합 수열 S(i) 혹은 S(i, j)를 구한다.

2. 계산 : 원하는 구간의 구간합을 계산한다.

 

전처리 단계의 경우 1차원 누적합일 경우 O(N)의 시간 복잡도와 공간 복잡도를 갖는다.

2차원 누적합은 전처리 단계에서 O(N^2)의 시간 복잡도와 공간 복잡도를 갖는다.

 

계산 단계에서는 두 경우 모두 O(1)의 상수 시간 복잡도를 갖는다.

 

 

참고 자료

- https://eine.tistory.com/entry/2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9-%EB%B6%80%EB%B6%84%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0