백준 11660번: 구간 합 구하기5 C++코드(누적합, PrefixSum)

//11660

#include<iostream>

using namespace std;

int numbers[1025][1025];

void prefixSum(int n){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            numbers[i][j] = numbers[i][j] + numbers[i-1][j] + numbers[i][j-1] - numbers[i-1][j-1];
        }
    }
}



int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n,m;
    int x1,y1,x2,y2;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> numbers[i][j];
        }
    }
    prefixSum(n);
    
    for(int i=0; i<m; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        cout << numbers[x2][y2] - numbers[x1-1][y2] - numbers[x2][y1-1] + numbers[x1-1][y1-1] << "\n";
    }

}

 

2차원의 누적합의 적용이 재밌는 문제이다. 

이러한 2차원의 누적합은 이미지 객체검출에서도 사용이 된다.

누적합을 구할때 arr[i] = arr[i] + arr[i-1] 인것과 달리 arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] 를 이용한다. 마지막에 arr[i-1][j-1]를 빼는 이유는 arr[i-1][j]과 arr[i][j-1]를 더하는 과정에서 2번 포함되어 한번 빼주는 용이다.