Search

구간 합

•
특정 배열이 있을 때 0번 인덱스부터 i번째까지의 합을 부분 합 혹은 누적 합(Partial Sum), i번째부터 j번째까지의 합을 구간합(Prefix Sum)이라 한다. 일반적으로 0번 인덱스부터 값을 더해나가며 부분 합을 구한 후, 원하는 구간 합을 구하기 위해 j번째 구간 합에서 i 번째 구간 합을 빼서 구한다.(Sum[ij] = sum[j] - sum[i])