구간 합 구하기4

코드

#include <string>
#include <iostream>
using namespace std;
int d[100002];
int N,M,sum=0,v;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i=1;i<=N;i++)
    {
        cin >> v;
        sum+= v;
        d[i] = sum;
    }
    int i,j;
    while(M--)
    {
        cin >> i >> j;
        cout << d[j] - d[i-1]<<'\n';
    }
    return 0;
}

• Prefix sum 개념이 사용
• prefix sum 이란?
  : 원하는 연속된 구간의 합을 구할 때 prefix sum의 차로 구할 수 있는 원리 --> O(1)의 시간복잡도