[알고리즘] 누적합 알고리즘

누적합 알고리즘

• DP 알고리즘에 속함
• 전처리를 한 후에는 1차원・2차원 배열의 합을 𝑂(𝟏) 만에 구할 수 있는 알고리즘

 

1차원 배열에서 누적합

• 음수 있어도 잘 동작함
  
  
• Dp 테이블 설계
  • psum[n]: 1~n번째 원소까지의 합
• 관계식
  • psum[n] = psum[n-1] + arr[n]
• a부터 b까지 원소의 합을 구하는 방법
  • psum[b] - psum[a-1]

 

2차원 배열에서 누적합

• 2차원 배열의 세로 길이를 N, 가로 길이를 M이라고 할 때, 𝑂(𝑁𝑀) 의 전처리를 수행하면 됨
  
  
• DP 테이블 설계
  • psun[n][m]: (1, 1)부터 (n, m)까지의 2차원 합
• 관계식
  • psum[n][m] = (psum[n][m-1] + psum[n-1][m] - psum[n-1][m-1]) + arr[n]
• (sy, sx)부터 (ey, ex)까지의 2차원 합 구하는 방법
  • psum[ey][ex] - (psum[ey][sx-1] + psum[sy-1][ex] - psum[sy-1][sx-1])

 

누적합 알고리즘은 언제 쓸까!?

• 1차원 배열의 누적합
  • 연속된 합의 구간을 여러 번 구해야 할 때
  • 𝑂(𝑁³) → 𝑂(𝑁²)
• 2차원 배열의 누적합
  • (직사각형 모양의) 2차원 합을 여러 번 구해야 할 때
  • 𝑂((𝑁𝑀)³) → 𝑂((𝑁𝑀)²)