부분 합

부분 합 : 배열의 각 위치에서 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열

어떤 구간의 평균, 분산 등을 구하기 위해서는 간단히 생각하면 해당하는 위치에 있는 애들을 다 더 해서 처리해야한다.

O(N)의 시간이 걸리지만, 이 방법을 여러 번 구현 한다면 전체 복잡도가 증가할 것이다. 

이 때, 부분 합을 이용하면 해당 구간의 합을 구하는 데에 O(1)로 해결할 수 있으므로 전체 복잡도를 줄일 수 있다.

 

arr[a]~arr[b] 까지 합 : psum[b] - psum[a-1]

c++ : STL에 partial_sum( ) 활용해도 됨

 

partialSum  : 전체 부분합 구하기, rangeSum : 배열의 a~b번째 합 구하기

vector<int> partialSum( vector<int> a){
	vector<int> result(a.size());
    result[0] = a[0];
    for(int i = 0; i < a.size(); i++){
    	result[i] = result[i-1] + a[i];
    }
    return result;
}

int rangeSum(vector<int> psum, int a, int b){
	if(a == 0)
    	return psum[b];
    return psum[b] - psum[a-1];
}

 

2차원 배열에서 부분합

 

2차원 배열에서도 부분합을 이용할 수 있다.

 

이를 이용하여 특정 구간의 합 ( (y1, x1) ~ (y2, x2) 까지 정사각형 구간의 합 )은 다음과 같이 구할 수 있다.

 

range_sum(y1, x1, y2, x2) = psum[y2][x2] - psum[y2][x1-1] - psum[y1-1][x2] + psum[y1-1][x1-1]

(직사각형을 생각하면 쉽다.)

 

int rangeSum(vector<vector<int> > psum, int y1, int x1, int y2, int x2){
	
    int result = psum[y2][x2];
    if(y1 > 0)
    	result -= psum[y1-1][x2];
    if(x1 > 0)
    	result -= psum[y2][x1-1];
    if(y1 > 0 && x1 > 0)
    	result += psum[y1-1][x1-1];
    return result;
}