[prefix sum] 백준 11660번 - 구간 합 구하기 5

 

 

 

 

pre 배열을 (1,1)에서 (i,j)까지 정사각형 모양의 값들의 합이라고 한다면

 

(a, b) ~ (c, d)의 값을 구한다고 한다면

답 : pre[c][d] - pre[c][a-1] - pre[a-1][d] + pre[a-1][b-1] 

 

그렇다면 pre 값들은 어떻게 구할 수 있을까 

 

마찬가지로 i j 이중 for문을 돌리면서 값을 받을 때 이전의 값을 참조하면 된다

 

pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + input

 

시간 복잡도 : O(max(N^2, M))

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

int N, M, start, ending;
// int numbers[1025][1025]; 사실상 필요가 없다
int pre[1025][1025];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>N>>M;
    int input;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin>>input;
            pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + input;
        }
    }
    int a, b, c, d;
    for(int i=0; i<M; i++){
        cin>>a>>b>>c>>d;
        cout<<pre[c][d]-pre[c][b-1]-pre[a-1][d]+pre[a-1][b-1]<<endl;
    }
}