11659번: 구간 합 구하기 4

문제링크

C++

#include <iostream>

using namespace std;

int N, M;

int arr[100001];
int sum[100001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }
    for (int idx = 1; idx <= M; idx++){
        int i, j;
        cin >> i >> j;
        cout << sum[j] - sum[i - 1] << "\n";
    }
}

• 누적 합 문제
• 매번 arr에서 합을 계산하면 $O(N^2)$이 된다.
• 따라서 각각의 input 숫자가 들어올 때마다 누적합을 구하면 input을 받는 데 $O(N)$이 걸리고
  • 매번 출력물을 계산할 때는 인덱스로 $O(1)$의 탐색을 하고 두 개의 누적합끼리 차분해주면 되기 때문에 마찬가지로 $O(N)$이 소요된다.
• 결국 최종적으로 $O(N)$