[알고리즘] 구간 합(Prefix Sum) / 11659 : 구간 합 구하기 4

💡 구간 합(Prefix Sum)이란?

수들의 나열에서 특정 구간의 합을 의미한다. 보통 1차원 배열에서 i번째~j번째 수까지의 합을 구할 때 유용하고 빠르게 이용할 수 있다.

구간 합 알고리즘

• 보통의 반복문을 사용하여 구간 [i, j]의 값을 더할 때, O(n)의 시간복잡도를 가진다.
• 구간 합 알고리즘은 이를 개선한 것으로, O(1)의 성능개선을 이끌어낸다.
  
  고등학교 수학시간에 배웠을 법한 공식이다. $1$~$n$까지의 수열의 합과, $1$~$n-1$까지의 수열의 합을 빼면 $a_n$이 나온다.
  이를 이용하여 i까지의 구간 합에 대하여,

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

공식을 이끌어낼 수 있다.

문제를 통해 이해해보기

---

문제 풀러 바로가기 >> 11659 구간 합 구하기(4)

💡 문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N
  
  
  

🤔 내가 생각한 아이디어

---

전략

음, 제한 조건의 수 최대가 10만이나 되는 걸 보니... O(n^2) 시간복잡도를 가지는 브루트포스로 풀면, 시간 초과가 발생할 것 같다.
그래서 아까 생각한 구간합 알고리즘을 생각해주어야 한다.

인풋으로

5 3
5 4 3 2 1
1 3
2 4
5 5

이 들어왔으니까..

• psum[1]=5
• psum[2]=5+4
• psum[3]=5+4+3
• psum[4]=5+4+3+2
• psum[5]=5+4+3+2+1

이 각 구간합 배열에 저장되고, 2번째 수~4번째 수 구간 수의 합은
psum[4]-psum[2-1]=9이므로

x번째 수~y번째 수 구간 수의 합은 다음과 같은 공식을 만족시킨다:
psum[y]-psum[x-1]

⚒️ 뚝딱뚝딱 설계

---

아까 설명했던 공식으로 수열 입력을 받을 때, 동시에 구간합을 구해버린다.
그럼 시간복잡도가 O(n) 정도다.
여기서 조금 주의해야 할 점이 psum 을 i번째 수까지의 수열의 합이라고 정의해야 하니까, i=1부터 시작함에 유의하자.

---

💻 정답 코드

#include <iostream>
using namespace std;
int n, m;
int a[100004];
int psum[100004]={0, };
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n >> m;
  for(int i = 1 ; i<= n; i++) {
    cin >> a[i];
    psum[i] = psum[i-1]+a[i]; //구간합 알고리즘
  }
  while(m--){
    int x, y;
    cin >> x >> y;
    cout << psum[y]-psum[x-1] << "\n";
  }
}