[백준] 11659번 구간 합 구하기 4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1

5 3

5 4 3 2 1

1 3

2 4

5 5

예제 출력 1

12

9

1

 

소스코드

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int n, m;
    int num[100001];
    int span[100001][2];
    int totalSum[100001]={0,};	// 입력받은 수까지의 전체 합이다.
    int sum=0;	// 구하고자 하는 구간 합이다.
    
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;i++) {
        scanf("%d", &num[i]);
        if(i==0) totalSum[i]=num[i];	// 숫자를 한 개 입력받았을 때 전체 합이다.
        else totalSum[i]=totalSum[i-1]+num[i];	// 숫자를 2개 이상 입력받았을 때 전체 합이다.
    }
    for(int i=0;i<m;i++) {
        scanf("%d %d", &span[i][0], &span[i][1]);
        if(span[i][0]==0) sum=totalSum[span[i][1]-1];	// 구간의 시작점이 1인 경우 totalSum이 sum이 된다.
        else sum=totalSum[span[i][1]-1]-totalSum[span[i][0]-2];	//구간의 시작점이 1이 아닌 경우 j번째까지의 totalSum에서 i-1번째까지의 totalSum을 뺀 값이 sum이 된다.
        printf("%d\n", sum);
    }
    return 0;
}

단순 for문을 이용하여 sum을 구하려는 경우 시간복잡도가 N*M으로, 시간초과가 발생하였습니다.

이를 해결하기 위해서 sum을 구하는 다른 방법을 고안해보았습니다.