Prefix sum

Prefix sum (구간합) Algorithm

- 구간 합이란? 배열 전체 값 중 L ~ R 번째 원소 구간의 합을 의미

- 구현 방법 : Prefix sum algorithm은 데이터 원소들을 누적해서 합한 값을 이용한다.

 

a1, a2, ..., aN 전체 N개의 숫자들이 있을 때 prefix sum의 i번째 값을 구하면

           

Pi = a1 + a2 + a3 + ... + ai

ex) 숫자 5개가 있다고 하자. {1,2,3,4,5}; 그러면

     prefix[6] = {0,1,3,4,10,15}; 

    만약 1번째부터 3번째까지 합을 구하고 싶다면 : prefix[3] - prefix[1-1] = 4 - 0 = 4 이런식으로 계산.

=> prefix sum의 차로 구간합을 계산한다.

     L ~ R까지 합을 구하고 싶으면 

     sum = prefix[R] - prefix[L-1]

- 구현 코드

#include <stdio.h>
using namespace std;
 
int N;
int sum[11];

int main()
{
    
    scanf("%d", &N);
 
    for (int i = 1; i <= 10; i++)
    {
        int temp;
        scanf("%d",&temp);
        sum[i] = sum[i - 1] + temp;
    }
 
 
    for (int i = 0; i < N; i++)
    {
        int a, b; // 구하려는 구간 합 범위 (a~b)
        scanf("%d %d", &a, &b);
 
        printf("%d\n", sum[b] - sum[a-1]);
    }
 
    return 0;
}

- 두 값의 차를 구하는 것이므로 O(1) 시간에 구간합을 구할 수 있다.