누적합이란?

코테 문제를 풀다가 누적합에 대해 알지 못하면 풀 수 없는 문제가 나와 글을 작성하게 되었다. 누적합의 기본 개념은 배열의 이전 값을 현재 값에 더해가며 배열에 저장된 수의 누적 합을 구하는 것이다. 이러한 누적합은 여러 방면으로 응용이 가능한데 간단한 것으로는 큰 범위의 배열의 구간합을 구할 수 있다.
0으로 초기화된 같은 크기의 새 배열을 만들어(new라 지칭) 기존 배열의 누적합을 구하여 저장해준다.(이하 old라 지칭)
new[i]=old[i]+new[i-1];
처럼 나타낼 수 있다. 이렇게 만들어낸 누적합 배열을 이용하여 i부터 j까지 (j-i>100000)와 같은 큰 범위의 합을 구해야 할 때 sum에 각 배열의 값을 일일이 더해주는 것이 아닌 new[j]-new[i]로 시간복잡도를 크게 줄이며 계산이 가능하다.
두번째 응용은 이 글을 쓰게 된 계기가 된 것인데 만약 자신이 배열의 i부터 j까지의 수에 2를 더하고싶다고 가정하여보자.
길이가 8인 배열에서 2부터 4까지의 수에 2를 더한다고 가정하면, 먼저 0으로 초기화된 길이 8 이상의 배열을 새로 만들어준다.
0 0 0 0 0 0 0 0
그리고 2에 2를 더하고 4+1에 -2를 더해준다.
0 0 2 0 0 -2 0 0
그 후 오른쪽으로 누적합 연산을 진행하면
0 0 2 2 2 0 0 0
로 원하던 범위에 2가 더해진 배열이 생기고 이를 원래 배열에 더하면 원하던 계산값을 얻을 수 있게 된다. 이러한 누적합 계산이 중요한 이유는 이처럼 원하는 범위에 원하는 숫자를 더해주는 연산이 여러개 있을 때, 새 배열에 법칙에 맞게 값을 계속해서 대입한 뒤 마지막에 누적합 연산을 한번만 해주고 원래 배열에 더해주면 원하는 계산값을 얻을 수 있기 때문이다.
원래 연산 한번마다 각 인덱스를 돌아다니며 값을 계산해주어야 하는 것이 연산마다 값만 대입하고 마지막에 누적합연산 한번으로 끝나기 때문에 시간복잡도가 크게 줄어드는 것이다.
이 아이디어는 2차원 배열에도 확장시킬 수 있는데 간단히 말하자면 (x1,y1)부터 (x2,y2)의 범위에 n을 더해주고 싶다고 가정하면 (x1,y1), (x2+1, y2+1)에 n을 더해주고 (x1,y2+1), (x2+1,y1)에 -n을 더해주면 된다. 예를 들어 행과 열의 길이가 4인 배열에서 (0,0)부터 (2,2)까지 3을 더해주고 싶다고 가정하면 0으로 초기화된 행열의 길이가 4인 배열을 새로 만든 뒤
3 0 0 -3
0 0 0 0
0 0 0 0
-3 0 0 3
과 같이 배열해주면 된다. 이제 이 배열을 순서 관계없이 위에서 아래로 한번, 왼쪽에서 오른쪽으로 한번 누적합 연산을 진행해주면,
3 3 3 0
3 3 3 0
3 3 3 0
0 0 0 0
이 되어 원하는 범위에 원하는 수가 더해진 배열을 갖게된다. 이를 원래 배열에 더해주면 원하는 계산값을 얻을 수 있다.
이 또한 1차원 배열과 마찬가지로 범위 연산이 많을 때 법칙에 맞게 새 배열에 값을 계속 대입해준 뒤 마지막에 누적합 연산을 한번만 진행하면 계산값을 얻을 수 있다. 이러한 아이디어가 필요한 대표적인 문제로는 카카오 블라인드 2022의 ‘파괴되지 않은 건물’ 문제가 있다. 이 문제의 해설을 참조하면 이러한 아이디어가 어떻게 활용되어야 하는지 알 수 있을 것이다.