누적합은 말 그대로 구간의 누적합을 구하는 문제입니다.
일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우O(n^2)의 시간복잡도를 갖기 때문에 입력의범위가 클 때 사용할 수 없습니다. 하지만 Prefix sum방식을 사용하면 O(N)으로 해결 할 수 있습니다.
누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있습니다.
예를들어 크기가 5인arr배열에서 3번index와 5번index구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b까지의 누적합] - arr[0~a-1까지의누적합]으로 표현할 수 있습니다.
그림을 보면 쉽게 이해할 수 있습니다. b-a구간의 누적합을 구하기위해선 b구간까지의 합- a-1구간까지의 합을 빼주면됩니다.
[3,5]구간의 누적합은??
1. 크기가 5인 배열선언( 인덱스1~5)
2. 각 인덱스값에 누적합 저장
3. 3번구간과 5번 구간 사이의 누적합을 구하려면 겹치는 1,2구간을 제외해줘야됨.
즉, 2번인덱스의 누적합을 빼줘야함.
위의 표에서 분홍색부분이 겹치는 부분,즉 빼줘야하는 부분이고 검은색부분이 답을 구할 범위다.
코드
#include<iostream>
using namespace std;
//인덱스1부터 가정하기위해 크기6으로생성
int arr[6] = { 0,7,6,3,2,1 };
int main()
{
//arr에 누적합을 저장한다.
for (int i = 1; i <=5; i++)
{
arr[i] = arr[i - 1] + arr[i];
}
//[3,5]구간 누적합 구하기
cout << arr[5] - arr[3 - 1] << '\n';
}
문제풀고 복습하기
https://www.acmicpc.net/problem/11441