누적 합

배열의 $i$번째 원소부터 $j$번째 원소까지의 합을 구하기 위해서는 단순히 for 문 한 번을 사용해 구할 수 있습니다.

하지만 이런 쿼리가 여러 번 계속될 경우 누적 합을 사용해 $O(1)$ 시간에 빠르게 구할 수 있습니다.

누적 합의 아이디어는 이전까지의 모든 원소의 합을 저장해두는 것입니다.

누적 합에서 주의해야 할 것은, 계산의 편의를 위해 index가 1부터 시작한다는 점입니다.

1차원 누적 합

1차원 누적 합은 원래 배열 v과 이전까지의 모든 원소의 합을 저장하는 배열 sum을 관리하면 됩니다.

a부터 b까지의 모든 원소의 합은 1부터 b까지의 모든 원소의 합에서 1부터 a - 1까지의 모든 원소의 합을 빼면 됩니다.

std::vector<int> v(n + 1);
std::vector<int> sum(n + 1);

for (int i = 1; i <= n; ++i) {
	std::cin >> v[i];
	sum[i] = sum[i - 1] + v[i];
}

// a번째 원소부터 b번째 원소까지의 합
int ans = sum[b] - sum[a - 1];

2차원 누적 합

2차원 누적 합은 1차원 누적합과 크게 다르지 않습니다.

전체에서 겹치는 부분을 빼주고 현재 원소를 더해주면 됩니다.

std::vector<std::vector<int>> v(n + 1, std::vector<int>(m + 1)); 
std::vector<std::vector<int>> sum(n + 1, std::vector<int>(m + 1)); 

for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= m; ++j) {
		std::cin >> v[i][j];
		sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v[i][j];
	}
}

// (a1, b1)에서 (a2, b2)까지의 합
int ans = sum[a2][b2] - sum[a2][b1 - 1] - sum[a1 - 1][b2] + sum[a1 - 1][b1 - 1];

백준 25682번: 체스판 다시 칠하기 2

체스판은 왼쪽 맨 위 칸이 검은색으로 시작하는 것과 흰색으로 시작하는 것 두 가지가 있을 수 있습니다.

따라서 두 가지 경우에 대해 2차원 누적합을 모두 구하면 됩니다.

백준 14846번: 직사각형과 쿼리

각 칸까지 등장한 1부터 10까지의 숫자의 개수를 저장하는 3차원 누적합을 사용합니다.