prefix-sum.md
구간 합
배열 arr 에 원소element 1 부터 10 까지 담겨 있다. 원소는 index 1 부터 담는다.
index : 1 2 3 4 5 6 7 8 9 10
value : 1 2 3 4 5 6 7 8 9 10
index 4 부터 index 7 까지의 value 를 더하면 arr[4] + arr[5] + arr[6] + arr[7] = 4 + 5 + 6 + 7 = 22 이다.
구간은 시작 index a 와 끝 index b 의 쌍 (a, b) 로 나타내고, arr[a] 부터 arr[b] 까지 더한 값을 구간 합이라 한다. 하나의 배열에서 여러 구간의 합을 구할 수 있다. 아래는 arr 의 세 구간과 각 구간 합이다.
(4, 7) → 4 + 5 + 6 + 7 = 22
(1, 10) → 1 + 2 + ... + 10 = 55
(3, 3) → 3 = 3
arr[0] 은 쓰지 않으며, 어떤 값이 들어 있어도 결과에 영향을 주지 않는다. 원소를 index 1 부터 담는 이유는 아래 누적 합에서 설명한다.
반복문으로 구하기
구간마다 arr[a] 부터 arr[b] 까지 차례로 더한다.
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main()
{
vector<int> arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<pair<int, int>> ranges = {{4, 7}, {1, 10}, {3, 3}};
for (auto [a, b] : ranges)
{
int sum = 0;
for (int j = a; j <= b; j++)
{
sum += arr[j];
}
cout << sum << '\n';
}
return 0;
}
22
55
3
구간 (4, 7) 은 덧셈을 4 번, (1, 10) 은 10 번 한다. 원소가 n 개이면 구간 하나에 최대 n 번 더하고, 구간 합을 m 번 구하면 최대 n × m 번 더한다. 시간 복잡도는 이다. 원소가 100,000 개이고 구간 합을 100,000 번 구하면 덧셈을 최대 10,000,000,000 번 한다. 구간이 길고 구간 합을 구하는 횟수가 많을수록 이 방식은 느려진다.
같은 원소를 구간마다 다시 더하는 것이 원인이다. 위 예시에서 (4, 7) 과 (1, 10) 은 arr[4] 부터 arr[7] 까지를 두 번 더한다.
누적 합
누적 합 배열 psum 의 index i 에는 arr[1] 부터 arr[i] 까지의 합을 담는다.
arr 를 index 1 부터 담았기 때문에 psum[i] 는 정확히 arr[i] 까지의 합이 되어, 두 배열의 index 가 일치한다.
psum[i - 1] 에는 이미 arr[1] 부터 arr[i - 1] 까지의 합이 담겨 있으므로, 여기에 arr[i] 하나만 더하면 psum[i] 가 된다.
위 그림은 arr 에 1 부터 10 까지 담았을 때의 psum 이다. 위의 작은 숫자가 index, 칸 안의 숫자가 value 이다. psum[4] 의 10 은 arr[1] 부터 arr[4] 까지인 1 + 2 + 3 + 4 이다. psum[0] 은 아무것도 더하지 않은 합이라 0 이다.
psum 은 index 1 부터 차례로 채운다. index 하나마다 덧셈을 한 번 하므로 이다.
for (int i = 1; i <= n; i++)
{
psum[i] = psum[i - 1] + arr[i];
}
누적 합으로 구간 합 구하기
psum[b] 는 arr[1] 부터 arr[b] 까지의 합이다. 이 합을 a 앞에서 둘로 나누면, 앞쪽은 arr[1] 부터 arr[a - 1] 까지인 psum[a - 1] 이고 뒤쪽은 구하려는 구간 합이다.
따라서 구간 합은 psum[b] 에서 psum[a - 1] 을 뺀 값이다.
위 그림은 a = 4, b = 7 일 때이다. 첫째 줄과 둘째 줄의 파란 칸은 각 psum 에 더한 원소이고, 셋째 줄의 파란 칸은 psum[7] - psum[3] 으로 남은 원소이다. psum[7] 은 arr[1] 부터 arr[7] 까지 더한 28, psum[3] 은 arr[1] 부터 arr[3] 까지 더한 6 이다. 28 에서 6 을 빼면 arr[1] 부터 arr[3] 까지가 지워지고 arr[4] 부터 arr[7] 까지의 합 22 만 남는다.
a = 1 이면 psum[0] 을 뺀다. 배열을 index 1 부터 채우고 psum[0] 을 0 으로 두었기 때문에, 이때도 같은 식으로 psum[b] 가 그대로 나온다. index 0 부터 채웠다면 psum[-1] 을 읽게 되어 a = 0 인 경우를 따로 처리해야 한다.
구간 하나에 뺄셈을 한 번 하므로 이다. psum 을 채우는 과 합치면 전체 시간 복잡도는 이다.
전체 코드
psum 은 vector<int> psum(n + 1, 0) 으로 만들어 psum[0] 을 0 으로 둔다. vector 대신 함수 안에서 int psum[11]; 처럼 일반 배열로 선언하면 값이 정해지지 않아 psum[0] 에 쓰레기 값이 들어갈 수 있다.
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main()
{
vector<int> arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<pair<int, int>> ranges = {{4, 7}, {1, 10}, {3, 3}};
int n = arr.size() - 1;
vector<int> psum(n + 1, 0);
for (int i = 1; i <= n; i++)
{
psum[i] = psum[i - 1] + arr[i];
}
for (auto [a, b] : ranges)
{
cout << psum[b] - psum[a - 1] << '\n';
}
return 0;
}
22
55
3