boj 11659 - 구간 합 구하기 4

목차

개요

설명

한계

코드

---

개요

해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다.

 

이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다.

---

설명

5 3
5 4 3 2 1
1 3
2 4
5 5

백준 예제로 방법을 간단하게 보겠습니다.

 

배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠.

 

처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... sum[n] = arr[n] + sum[n-1] 과 같은 점화식으로 sum 배열을 $O(N)$에 만들 수 있습니다.

이제 부분 합은 어떻게 구하면 될까요?

 

간단하게 sum배열만 사용하면 구할 수 있습니다.

1 3
2 4
5 5

한 줄마다 입력을 i, j 로 받았다고 가정합시다.

 

i=2, j=4인 2 ~ 4의 경우 arr[2] + arr[3] + arr[4] = sum[4] - sum[1] = 9 와 같습니다.

즉, sum[j] - sum[i-1]을 구해야 하는 것이죠.

 

이는 수식적으로 표현하면 다음과 같습니다.

$\Sigma_{i}^{j} {arr[k]} = \Sigma_{0}^{j} {arr[k]} - \Sigma_{0}^{i-1} {arr[k]} = sum[j] - sum[i-1]$

---

한계

만약 여기서, arr 배열에 있는 어느 원소의 값이 갑자기 중간에 바뀌게 되면 어떻게 될까요?

 

올바른 결과를 도출하기 위해, 바뀐 원소를 기준으로 그 뒤의 모든 sum을 다시 계산해야 합니다.

현재 arr[1]이 5인데, 만약 이 값이 105로 바뀐다면 sum[1] ~ sum[5]에 모두 100을 다시 더해줘야 하지요.

 

이런 일이 빈번하게 생기면 ($k$ 번 생기면), sum배열을 갱신하는 데만 $O(kn)$의 비용이 듭니다.

 

따라서 이를 효율적으로 하고자, [세그먼트 트리(Segment Tree)]가 고안 되었습니다.

---

코드

※주의할 점

1. 편의를 위해, 입력받은 값은 arr[1] ~ arr[100000]에 저장합니다. 따라서, arr배열은 100,001 개의 공간을 갖고 있어야 합니다. 이는 sum도 마찬가지입니다.

#include<stdio.h>
int arr[100001],sum[100001];
int main(){
    int n,m,i,a,b;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        sum[i]=sum[i-1]+arr[i];
    }
    for(i=0;i<m;i++){
        scanf("%d %d",&a,&b);
        printf("%d\n",sum[b]-sum[a-1]);
    }
}