누적합 알고리즘 (Prefix Sum Algorithm)

• 누적합 알고리즘은 구간합을 빠르게 계산하기 위해 사용되는 기법이다.
• 주어진 배열의 구간합을 O(1) 시간 복잡도로 구할 수 있다. 이를 위해 먼저 누적합 배열을 생성

기본 개념

• 정의: 누적합 배열은 원래 배열의 각 원소까지의 합을 저장한 배열
• 목적: 구간합을 빠르게 구하기 위해 사용됌.
• 사용법: 특정 구간 [A, B]의 합을 구할 때, B까지의 누적합에서 A-1까지의 누적합을 뺍니다.

예시

• 주어진 배열: [1, 2, 3, 4, 5]
• 누적합 배열: [1, 3, 6, 10, 15]

1. 방법 1:

   • 각 단계별로 누적합을 구합니다.
   • 예시:

     1
     1 + 2
     1 + 2 + 3
     1 + 2 + 3 + 4
     1 + 2 + 3 + 4 + 5
     

2. 방법 2 (더 효율적인 방법):

   • 이전 단계의 누적합에 현재 원소를 더합니다.
   • 예시:

     1
     1 + 2
     3 + 3
     6 + 4
     10 + 5
     

구간합 계산 방법

• 구간합 [A, B] 계산:
  1. 누적합 배열을 구합니다.
  2. 구간합은 B까지의 누적합에서 A-1까지의 누적합을 뺀다.
  • 수식: sum(A, B) = prefix_sum[B] - prefix_sum[A-1]