구간 합 구하기 알고리즘[1]

c++ 에서 시간 단축을 위해 쓰이는 코드

멀티스레드나 실제 시스템을 구축할 때, 쓰이진 않는다.

백준 11659번 c++

ios::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

 

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int su, quiz;
    cin >> su >> quiz;
    int S[100001] = {};

    for (int i = 1; i <= su; i++) {
        int temp;
        cin >> temp;
        S[i] = S[i - 1] + temp;
    }

    for (int i = 0; i < quiz; i++) {
        int start, end;
        cin >> start >> end;
        cout << S[end] - S[start - 1] << "\n";
    }
}

 

합 배열 알고리즘 외우자

: S[i] =S[i-1] + A[i]

구간 합 i에서 j까지

: S[j] - S[i-1]