[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 #include // for copy #include // for multiplies #include // for partial_sum #include // for vector using namespace std; int..
