[Algorithm] Prefix Sum 구간합

🍒구간합이란?

-부분합 : 0~k 까지의 합

-구간합 : a~b 까지의 합

구간합은 말 그대로 시작점 a 부터 끝점 b까지 사이의 모든 값의 합을 의미한다.

 

🍒구간합 적용

구간합을 구하는 문제인데 구간사이의 수의 개수가 5천만개라면?

이러한 요청이 2천만개라면?

이중반복문을 사용해서 해결하면 분명 시간복잡도가 O(N^2)으로 오래걸리는 문제가 생긴다.

int n; //요청 수
scanf("%d", &n);

while(n--){
	int a, b;
    scanf("%d %d", &a, &b);
    
    int sum = 0;
    for(int i=a; i<=b; i++){
    	sum += arr[i];
    }
	cout << sum << endl;
}

prefix Sum 알고리즘을 적용하면 1개의 반복문으로 문제를 해결 할 수 있다.

즉, 미리 합계를 계산해놓고 sum배열에 저장해 놓는다. 이때 시간복잡도는 O(N)이 소요된다.

for(int i=0; i<10; i++)
{
	if(i == 0){
    	sum[i] = arr[i];
    }else{
    	sum[i] = sum[i-1] + arr[i];
    }
}

int n; //요청 수
scanf("%d", &n);

while(n--){
	int a, b;
    scanf("%d %d", &a, &b);
    cout << sum[b] - sum[a-1];
}

총 배열의 길이가 10이라면 10번째 수까지 합을 모두 구해놓고 [a, b] 구간의 합계 = sum[b] - sum[a-1]로 구하면된다.

---

✔참고

www.crocus.co.kr/843

구간 합(Prefix Sum) 알고리즘