부분합이란?
배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열
이제부터 부분합 배열을 psum[]이라고 하겠습니다. 또한,
psum[-1] = 0;
psum[0] = A[0];
psum[k] = ([0, k] 구간의 합)
으로 두겠습니다.
부분합 시간복잡도?
O(1) (그냥 psum[b] - psum[a-1] 하면 됩니다.)
문제 풀며 느낀 팁
부분합 문제인거 같은데 뭔가 잘 안풀린다면, 부분합 배열을 정렬해보자.
Sum(a,b) = psum[b] - psum[a - 1] 인데,
구간의 합이 특정한 값이 되어야 한다던가, 최소일 때를 찾아야 한다거나 할 때 유용하다.
ex)
구간합이 0인 구간을 구해라(정렬한 후에 같은 값이 몇 개 있는지 세면 됨)
구간으로 주문할 수 있는 인형가게에서 K명의 어린이에게 공평하게 나눠줄 수 있는 가짓수를 구해라
(구간합에 mod K 을 취한 후 구하면 됨)
2차원 부분합도 가능
psum[y, x] = ((0,0)을 왼쪽 위 칸, (y,x)를 오른쪽 아래 칸으로 갖는 직사각형 구간의 원소의 합
sum(y1,x1,y2,x2) = psum[y2,x2] - psum[y2, x1 - 1] - psum[y1 - 1, x2] + psum[y1 - 1, x1 - 1];
24장의 펜윅트리와 구별 할 점
원 배열의 원소를 수정할 일이 적거나 없다면 부분합 배열로 문제 해결(계산 : O(1), 수정 : O(n))
원 배열의 원소를 수정할 일이 많다면(or 수정하고 부분합 구하고를 반복한다면) 펜윅 트리가 유리(계산 : O(log n), 수정 : O(log n))
