누적합,구간합 알고리즘(Prefix Sum)
배열의 일부 구간의 합을 빠르게 구할 수 있게 해주는 알고리즘이다. N개의 원소가 주어졌을 때 반복문을 통해 일정 구간의 합을 구하고자 하면 O(N)의 시간 복잡도가 걸리지만 부분합 알고리즘을 사용하면 O(1) 시간 복잡도로 문제를 해결할 수 있다.
아래와 같은 배열이 있다고 하자
배열의 누적합을 구하면 다음과 같다. O(1)로 이를 구할 수 있다.
만약 1~3까지의 부분합을 구하고자 한다면 아래와 같이 구할 수 있다. 어떤 구간을 구하고자 하더라도 뺄셈을 통해 빠르게 구할 수 있게 된다.
1차원 누적합
이 아이디어를 활용해서 어떤 구간에 값을 더하고자 할때 이를 빠르게 구하는 방법에 대해 알아보자. 매번 구간에 값을 더하게 되면 O(N)의 복잡도를 가지게 된다. 부분합 알고리즘을 통해 복잡도를 줄일 수 있다. 여기서부터 여기까지 값을 더할거야 라고 표시를 해놓는 것이 아이디어이다. 예시를 통해 살펴보자
만약 2~5까지 3을 더하고자 한다면 다음과 같이 표시해 둔다.
이후 구간합을 구한다. 원하는 결과가 나오는 것을 알 수 있다.
이는 여러 구간에 값을 더하고자 할 때 효력이 나타난다. [2, 5] 에 3을 더하고 [0, 3] 에 2를 빼고 [4, 7] 에 4를 더한다고 하자
아래와 같이 표시를 할 수 있다. 구현의 편의를 위해 배열의 길이보다 1길게 만들어서 표시하면 더 편하다.
마지막에 누적합을 구하면 원하는 결과가 나온다.
2차원 누적합
1차원의 아이디어를 넓혀서 2차원에도 적용이 가능하다. 아래 순서로 2차원 배열의 누적합도 쉽게 구할 수 있다.
관련 문제
앞으로 연속되는 구간의 합을 구하고자 할 일이 있다면 누적합 알고리즘을 생각하자.