누적합(Prefix Sum)

누적합 (Prefix Sum)

배열의 시작부터 각 인덱스까지의 원소들의 합을 미리 계산해 두는 것. 예를들어, 배열이 [a,b,c,d]라면 누적합 배열은 [a,a+b,a+b+c,a+b+c+d]가 된다. 이 누적합 배열을 사용하면 임의의 구간 [i,j]의 합을 prfixSum[j] - prefixSum[i-1] (단, i > 0)으로 빠르게 계산할 수 있다. 2차원 배열에서도 이 개념을 확장해서 사용할 수 있으며, 이 경우 특정 구역의 합을 빠르게 계산할 수 있다.

1차원 Prefix Sum

2차원 Prefix Sum