백준 11659 구간 합 구하기 4 / C++

문제 : 11659

풀이 point

평범하게 매 테스트케이스마다 값을 구하면 시간 복잡도는 O(NM)이므로 시간초과다.

시간초과를 피하기 위해 미리 계산해두는 방식을 생각해볼 수 있다. 누적합을 구해놓은 뒤 그 누적합을 통해 각 문제에 해답을 구할 수 있다.

ex) 5 4 3 2 1
-> 5 9 12 14 15

1 3의 경우에는 12를 주면 된다.
2 4의 경우애는 4까지의 누적합 - 1까지의 누적합(2에서부터 4까지기 때문) = 9를 주면된다.
5 5의 경우에는 5까지의 누적합 - 4까지의 누적합(5에서부터 5) = 1을 주면 된다.

코드

//백준 11659, 구간 합 구하기 4

#include <iostream>

int arr[100'001];

int main (){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    int N, M;
    std::cin >> N >> M;
    for(int i{1}; i<=N; ++i){
        std::cin >> arr[i];
        arr[i] = arr[i-1] + arr[i];
    }
    

    while(M--){
        int i, j;
        std::cin >> i >> j;
        std::cout << arr[j] - arr[i-1] << '\n';
    }

    return 0;
}