[구간 합 문제란 ?] 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제이다. 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정하고, 두번째 수부터 네번째 수까지의 합은 20 + 30 + 40 = 90 이다. 구간 합 문제를 빠르게 계산하기 위해 접두사 합(Prefix Sum)을 활용한 알고리즘을 사용할 수 있다. [접두사 합이란 ?] 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것이다. 즉, 접두사 합을 활용한 알고리즘 동작과정은 다음과 같다. 1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다. 2. 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1] 이다. ..
