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

https://www.acmicpc.net/problem/11659

풀이

매번 i번째부터 j번째까지의 수를 구하기에는 시간이 너무 오래 걸리므로 투포인터 방법을 사용했다.

누적합을 저장하는 배열 sum을 만든다. 즉, sum의 i번째 원소는 1번째 수부터 i번째 수까지의 합이다.

문제에서 요구하는 i번째 수부터 j번째 수까지의 합은 sum[j] - sum[j-1] 으로 구한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, x, i, j;
    cin >> n >> m;
    
    vector<int> sum(n+1, 0);
    for(int i=1; i<=n; i++) {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    
    while(m--) {
        cin >> i >> j;
        cout << sum[j] - sum[i-1] << "\n";
    }
    
    return 0;
}