N명의 시험 성적이 내림차순으로 저장되어있는 배열 score이 있다고 할때 a등에서 b등까지 평균점수를 계산하자 평균점수를 계산할때는 score[a]에서 score[b]까지 더하고 b-a+1를 나누면 됩니다. 하지만 이 방법은 O(N)이 걸리게 됩니다. 따라서 부분합 배열 Sum을 사용하면 O(1)에 문제를 해결할 수 있습니다. 0 1 2 3 4 5 6 7 8 score 1 2 3 4 5 6 7 8 9 sum 1 3 6 10 15 21 28 36 45 부분합을 구현하는 함수는 다음과 같습니다 vector partialSum(vector score){ vectorret; int temp=0; for(int i=0;i0) ret-=psum[y1-1][x2]; if(x1>0) ret-=psum[y2][x1-1..