연속된 부분 합(연속합) - 2 (Prefix Sum)

※ 구간합을 구하는 효율적인 방법

연속된 부분 합(연속합) - 1 (완전 탐색) 

연속된 부분 합(연속합) - 2 (Prefix Sum)

연속된 부분 합(연속합) - 3 (DP)  

[구간합] Sum of sub-matrix (2D Array) 

Prefix Sum

: psum[i] = 첫번째 원소부터 i 번째 원소까지의 구간 합

  A[i] = psum[i] - psum[i-1]

  ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4

psum[]을 이용한 특정 구간 합

▶ 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8

    ↔ psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지의 합) = (8 ~ 9까지의 합)

 

Reference

- 연속된 부분 합(연속합) - 1 (완전 탐색) 

- 연속된 부분 합(연속합) - 2 (Prefix Sum)

- 연속된 부분 합(연속합) - 3 (DP)  

- [구간합] Sum of sub-matrix (2D Array) 

 

관련 문제

- [Jungol] 2497 수열

- [BOJ] 2670 연속부분최대곱

- [BOJ] 1912 연속합

- [BOJ] 10986 나머지 합