[C++/STL] 부분 합 partial_sum( )

 

 

특정 구간의 합을 O(1)에 구하고 싶을 때, 부분 합(partial sum)을 미리 구해놓으면 가능하다.

부분 합은 다음과 같다.

 

i	0	1	2	3	4
v	1	2	3	4	5
psum	1	3	6	10	15

 

자 이제 여기서 특정 구간의 합만 구하는 방법은..? 원하는 구간 [a-b] (psum[-1] = 0 이라고 가정)

psum[b] - psum[a-1] 

---

부분합은 for 문을 사용해서 O(n)의 시간으로 직접 구할 수도 있고 c++ 의 경우에는 STL을 사용할 수 있다.

#include <iostream>
#include <algorithm>  // for copy
#include <functional> // for multiplies
#include <numeric>    // for partial_sum
#include <vector>     // for vector
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    vector<int> v = {1,2,3,4,5};
    vector<int> sum(v.size());
    vector<int> mult(v.size());
    
    partial_sum(v.begin(), v.end(), sum.begin());
    partial_sum(v.begin(), v.end(), mult.begin(), multiplies<int>());
    
    for(int i = 0; i < sum.size(); i++)
        cout << sum[i] << " ";
    cout << endl;
    for(int i = 0; i < mult.size(); i++)
        cout << mult[i] << " ";
    cout << endl;
    
    return 0;
}

 

#include <numeric> 에 있는 partial_sum( ) 함수를 이용하여 부분 합을 쉽게 구할 수 있다.

부분 합을 담을 벡터(배열)을 미리 그 크기만큼 할당을 해주는 것이 중요하다.

 

#include <functional> 안의 multiples<int>( ) 함수를 이용하여 누적 곱도 구할 수 있다.