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

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

 

문제 해석

• 누적합을 이용한 구간합 구하기

알고리즘 분류

• 누적합

풀이

• 누적합을 미리 계산해 두고 여러개의 구간합을 O(1)로 출력한다
• sum[j] - sum[i-1]

코드

#include <iostream>

using namespace std;

int main()
{
    int N = 1;
    int M;
    int ii, j;
    cin >> N >> M;

    int arr[N+1];
    int sum[N+1];

    for (int i=1; i<=N; i++) {
        cin >> arr[i];
    }

    sum[1] = arr[1];

    for (int i=2; i<=N; i++) {
        sum[i] = sum[i -1] + arr[i];
    }

    for (int i=0; i<M; i++) {
        cin >> ii >> j;
        cout << sum[j] - sum[ii] << "\n";
    }


}