누적합(prefix sum)

[devLupin]

prefix sum

---

• 수열 n개가 주어질 때, 해당 수열에서 x개마다의 합을 구하는 알고리즘
• 2중 for loop로 $O(N^2)$의 시간 소모
• $O(N)$ 알고리즘

예시

• 1, 2, 3, 4, 5의 수열
• 2번째부터 4번째까지의 누적합을 구해야 한다면?
• 프로세스
  • (최초 1회) 전체 누적합을 구한다.
  • 2번째부터 4번째까지의 합은 4번째까지의 합에서 첫 번째 까지의 합을 빼주면 된다.
• 점화식
  • dp[i] - dp[i - x]
  • i는 구하고자 하는 누적합의 마지막 위치
  • x는 누적합 개수

[devLupin]

• 수열 n개를 입력받고, x개의 구간마다 누적합을 구한다고 가정

int n, x;
cin >> n >> x;

vector<int> v(n + 1);
vector<int> dp(n + 1);

// 수열 입력받고, 메모이제이션
for (int i = 1; i <= n; i++) {
    cin >> v[i];
    dp[i] = (i > 0) ? dp[i - 1] + v[i] : v[i];
}

// 누적합 구하기
for (int i = x; i <= n; i++)
    int prefix_sum = dp[i] - dp[i - x];