알고리즘 설명
누적합 알고리즘은 배열에서 구간합을 구할 때 적은 비용으로 구할 수 있는 알고리즘이다.
| 1 | 2 | 5 | 2 | 4 | 3 | 1 |
보통 위와 같은 배열에서 합을 구하기 위해서는 인덱스0 부터 더하고자 하는 인덱스까지 모두 더해주어야 한다.
예를들어, 인덱스 0 ~ 4까지의 합은 1 + 2 + 5 + 2 + 4 를 더해야 하고 인덱스 3 ~ 6까지의 합은 2 + 4 + 3 + 1 이 된다.
하지만, 누적합 알고리즘을 사용한다면 누적합 배열을 구하면 이후의 구간합을 구하는 연산은 O(1) 시간복잡도로 해결이 가능하다.
구간합은 아래와 같다.
| 1 | 3 | 8 | 10 | 14 | 17 | 18 |
여기서 인덱스 0 ~ 4까지의 합은 구간합배열[4] 가 되고, 인덱스 2 ~ 4 까지의 합은 구간합배열[4] - 구간합배열[1] 이 된다.
즉, 구간합을 구한 뒤에는 빼기 연산 한번이면 다른 구간합들을 구할 수 있다.
- 구간합을 여러번 구해야 할 때 사용하는 알고리즘
- 인덱스 N부터 인덱스 M까지의 합: 구간합배열[M] - 구간합배열[N-1]
관련문제
| 플랫폼 | 링크 | 요약 | 풀이 | 복습 |
| 백준 | https://www.acmicpc.net/problem/2143 | 각 인덱스를 시작 인덱스로 지정하면서 구간합을 구하는 문제 | ||
| 백준 | https://www.acmicpc.net/problem/2632 | 각 인덱스를 시작 인덱스로 지정하면서 구간합을 구하는 문제(원형큐) |