부분 합

배열의 각 위치에 대해서, 배열의 시작부터 현재 위치까지의 원소의 합을 구한 배열

#include <iostream>
#include <vector>
using namespace std;

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;
}

int rangeSum(const vector<int>& psum, int a, int b) {
	if (a == 0) return psum[b];
	return psum[b] - psum[a - 1];
}

앞의 값에서 현재 값을 더하며 부분합 배열을 구하고, 이를 활용해서 구간 합을 위와 같이 구할 수 있다.

분산을 구할 때도 쉽게 쓰일 수 있는데, 아래와 같은 함수로 구현 가능하다

// a에서 b까지의 범위에서 분산을 구한다. 
double variance(const vector<int>& sqpsum, const vector<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);
}

sqpsum 은 A 배열의 제곱의 부분합 벡터이다.

2차원으로의 확장

#include <iostream>
#include <vector>
using namespace std;

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;
}

이차원 배열에서 특정 그리드에 속하는 배열의 합을 구하는 과정

크리스마스 인형 (CHRISTMAS)