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

문제

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

11659번: 구간 합 구하기 4

 

 

풀이

• 합 배열 공식 : S[i] = S[i - 1] + A[i]
• 구간 합 공식 : S[j] - S[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> A(N);
  vector<int> sum(N, 0);
  for(int n = 0; n < N; n++)
  {
    cin >> A[n];
    
    // 구간 합 구하기
    if(n == 0)
    {
      sum[n] = A[n];
    }
    else
    {
      sum[n] = sum[n - 1] + A[n];
    }
  }

  for(int n = 0; n < M; n++)
  {
    int i, j;
    cin >> i >> j;	// 질의 범위 받기

    cout << sum[j - 1] - sum[i - 2] << "\n";	// 부분 합 출력
  }
  
  return 0;
}