partial_sum
partial_sum (부분 합계)
범위의 접두 누적 합계(부분 합)를 계산해 출력 범위에 저장하는 알고리즘이에요. <numeric> 헤더에 있어요.
출처: cppreference
본문
partial_sum은 입력 범위 [first, last)의 각 위치에, 처음부터 그 위치까지의 누적 합을 d_first에 저장해요.
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first ); // (1)
사용자 정의 이진 연산 버전도 있어요.
template< class InputIt, class OutputIt, class BinaryOp >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOp op ); // (2)
-
- 덧셈으로, 2)
op로 누적해요.
- 덧셈으로, 2)
- 출력의 첫 원소는 입력의 첫 원소와 같고, 각 후속 원소는 이전 누적 결과에 현재 원소를 결합한 값이에요.
std::vector<int> v{1, 2, 3, 4, 5};
std::vector<int> ps(5);
std::partial_sum(v.begin(), v.end(), ps.begin());
// ps == {1, 3, 6, 10, 15}
접두 합(prefix sum)을 구하는 알고리즘으로, 누적 합을 순서대로 얻고 싶을 때 써요. 병렬·일반화 버전으로는 inclusive_scan(C++17)이 더 새로워요.