부분 합(partial sum)

부분 합부분 합 : 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열scores[] : N 명의 시험 성적을 내림차순으로 정렬해 둔 배열psum[] : scores[]의 부분 합psum을 미리 계산해 놓으면 scores[]의 특정 구간의 합을 O(1)에 구할 수 있다.즉 scores[a]부터 scores[b]까지의 합은 psum[b] - psum[a-1]이다.중요한 게 psum[a-1]이다.간혹 psum[a]로 착각하는 경우가 많다.구현 코드위에 있는 걸 그대로 만들었을 때 나오는 코드부분 합을 구하는 함수까지 추가하면int rangesum 함수를 보면 if(a==0)이 있다.기본적으로 psum[a-1]이기에 a가 0 일 때 psum[-1]이 되므로음수를 처리하지 않기 위..........

원문링크 : 부분 합(partial sum)