17_code_snippet.cpp

// 코드 17.1 부분합을 계산하는 함수와 이를 이용해 구간합을 계산하는 함수의 구현

// 주어진 벡터 a의 부분합을 계산한다
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;
}

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

// 코드 17.2 배열의 부분합과 제곱의 부분합을 입력받고
// 특정 구간의 분산을 계산하는 함수의 구현

// A[]의 제곱의 부분 합 벡터 qqpsum, A[]의 부분 합 벡터 psum이 주어질 때
// A[a..b]의 분산을 반환한다
double variance(const vector<int>& sqpsum,
	const vecotr<int>& psum, int a, int b) {
	// 우선 해당 구간의 평균을 계산한다
	double mean = rangeSum(psum, a, b) / double(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);		
}

// 코드 17.3 부분 합을 이용해 2차원 배열의 구간 하을 구하는 함수의 구현

// 어떤 2 차원 배열 A[][]의 부분합 psum[][]이 주어질 때,
// A[y1, x1]과 A[y2, x2]를 양 끝으로 갖는 부분 배열의 합을 반환한다
int gridSum(const vector<vector<int> >& psum, int y1, int x1, int y2, int x2) {
	int ret = psum[y2][x2];
	if (y1 > 0)
		ret -= psum[y1 - 1][x2];
	if (x1 > 0)
		ret -= psum[y2][x1 - 1];
	if (y1 > 0 && x1 > 0)
		ret += psum[y1 - 1][x1 - 1];
	return ret;
}