(11659) 구간 합 구하기 4

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

단계별로 풀어보기

22단계(누적 합) 1번째

 

 

 

단독으로 쓰이기보단 다른 문제에서 필요한 테크닉으로 주로 쓰이는 누적 합 개념이다.

s[k]를 수열의 1번째부터 k번째 원소까지 더한 누적합이라고 하자. s[0]=0이다.

이때 수열의 i번째 원소부터 j번째 원소까지의 합은 반복문으로 구하면 O(N)이 걸리지만,

누적합을 이용하면 s[j]-s[i-1]로 O(1)만에 바로 구할 수 있다.

누적합에서 s[0]을 (개념적으로 공집합 원소의 합인) 0으로 두는 이유가 이것이다. s[0]=0이라면 i=1일 때에도 계산이 쉽기 때문이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> s(n+1);
  
  for(int k=1;k<=n;k++){
    cin >> s[k];
    s[k]+= s[k-1];
  }
  
  while(m--){
    int i, j;
    
    cin >> i >> j;
    
    cout << s[j]-s[i-1] << "\n";
  }
  
  return 0;
}