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

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

11659번: 구간 합 구하기 4

---

풀이 과정

N개의 수가 주어졌을 때, i번째 수부터 j번째 수 까지의 합을 구하는 문제이다.

 

개수 N이 최대 10만, 합을 구해야 하는 횟수 M이 최대 10만이다. i부터 j까지 일일이 더해보면서 합을 구하면 0번째 수부터 10만번 - 1째 수까지 다 더하라는 명령이 10만번 들어오면 연산 횟수가 너무 많아진다. O(N^2) 방법으로는 답을 해결할 수 없다.

 

구간을 입력받고 구간의 누적합을 한번 저장해놓으면 구간 합을 구하는 연산이 O(1)로 줄어든다. D[i]를 i번째 원소까지의 누적합이라고 하면 i번째 수부터 j번째 수까지의 합을 D[j-1] - D[i-2]로 바로 구할 수 있다.

---

소스 코드

#include <iostream>
using namespace std;

int A[100001];
int D[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, num, i, j;
    cin >> N >> M;

    for (int a = 0; a < N; a++) {
        cin >> num;
        A[a] = num;
    }

    D[0] = A[0];
    
    for (int a = 1; a < N; a++) {
        D[a] = D[a-1] + A[a];
    }

    for (int a = 0; a < M; a++) {
        cin >> i >> j;
        if (i >= 2) {
            cout << D[j-1] - D[i-2] << '\n';
        } else {
            cout << D[j-1] << '\n';
        }
    }

    return 0;
}