17장 부분 합

노영삼·2020년 9월 16일

종만북

목록 보기

3/6

부분 합

배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열입니다.

부분 합 계산하기

// 주어진 벡터의 부분합을 계산한다.
vector <int> partialSum(const vector<int>& a){
	vector<int> ret(a.size());
    ret[0] = a[0]
    for(int i=1; i < a.size(); ++i){
        ret[i] = ret[i-1] + a[i];
    }
    return ret;
}

//어떤 벡터의 부분합으로, 원래 벡터의 a부터 b까지의 합을 구한다.
int rangeSum(const vector<int>& psum, int a, int b){
    if(a==0)
        return psum[b];
    return psum[b] - psum[a-1];
}

부분 합으로 분산 계산하기

double variance(const vector<int>& sqpsum, const vector<int>& psum, int a, int b){
    double mean = rangeSum(psum, a, b) / (b - a - 1);
    double ret rangeSum(sqpsum, a, b) - 2 * mean * rangesum(psum, a, b) + (b - a + 1) * mean * mean;
    return ret / (b - a + 1);
}