Prefix Sum을 사용하려면 먼저 Prefix Array를 생성해야 합니다. Prefix Array는 원본 배열의 각 원소에 대해, 해당 원소까지의 합을 저장하는 배열입니다.
예를 들어, 원본 배열이 [3, 2, 5, 1, 7]일 때, Prefix Array는 [3, 5, 10, 11, 18]가 됩니다.
Prefix Array를 생성하는 방법은 다음과 같습니다.
1. 원본 배열의 첫 번째 원소는 Prefix Array의 첫 번째 원소와 같습니다.
2. 원본 배열의 두 번째 원소부터, Prefix Array의 해당 인덱스에 원본 배열의 해당 인덱스까지의 합을 저장합니다.
예를 들어, 원본 배열의 두 번째 원소는 2입니다. Prefix Array의 두 번째 원소는 원본 배열의 첫 번째 원소와 두 번째 원소의 합인 3 + 2 = 5입니다.
Prefix Array를 생성한 후, 특정 구간의 합을 계산할 때는 Prefix Array의 해당 인덱스에서 해당 인덱스까지의 합을 저장한 원소와, 해당 인덱스 이전의 원소의 합을 저장한 원소의 차이를 계산하면 됩니다.
예를 들어, 원본 배열의 2번째부터 4번째까지의 합을 계산하려면, Prefix Array의 4번째 원소 (11)와 2번째 원소 (5)의 차이를 계산하면 됩니다. 결과는 11 - 5 = 6이 됩니다.
2025-03-04 16:52