구간합 구하기

☝🏻 prefixSum 구할때

// #include<bits/stdc++.h>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;
int a[100004],b,c,psum[100004],n,m;
int main() {
    cin >> n >> m;
    for(int i=1;i<= n;i++) {
        cin >> a[i];
    }
    for (int i=0; i<m; i++) {
        cin >> b >> c;
        int sum = 0;
        for(int j =b;j <= c;j++) sum += a[j];
        cout << sum << '\n';
    }

    return 0;
}

위와 같이 구간합을 구할 수 있다.
위의 코드 로직을 설명하면 다음과 같다.

1. 배열을 하나 만든다.
2. 그 배열에는 1~N까지의 수를 넣음
3. 두번째 배열을 만든다.
4. 그 배열에는 첫번째 배열의 요소를 더해가면서 구간합을 배열에 저장한다.

하지만 위의 코드의 가장 큰 문제는 시간복잡도가 크다는 것이다.
n과 m의 크기가 100000일 경우를 생각해보자.

그렇다면 시간복잡도는 100,000 * 100,000의 크기를 가진다.
즉, 위의 프로그램의 시간복잡도는 100억이다.

따라서 다른 방법을 사용해야한다.
그렇기에 필요한 것이 prefixSum이다.

먼저 코드를 보자.

// #include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
int a[100004],b,c,psum[100004],n,m;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }
    for (int i = 0; i < m; i ++) {
        cin >> b >> c;
        cout << psum[c] - psum[b-1] << "\n";
    }

    return 0;
}

위의 코드는 psum이라는 배열을 선언해두고, 구간합을 다음의 공식을 사용한다.

\[현재요소까지의 구간합 = 전요소까지의 구간합 + 현재 요소\]

이를 이용하여 다음과 같이 표현할 수 있었다.

psum[i] = psum[i-1] + a[i];

이를 통해 기존 100억이라는 시간복잡도가
위의 코드에서는 100,000이라는 값을 가지게 된다.