while (1): study();

만약 [left index, right index]로 구성된 M개의 쿼리에 대해 구간합을 구하고자 한다면, 단순 반복으로는 시간복잡도가 O(NM)이 됩니다. 따라서 데이터의 개수가 1,000,000개인 경우에는 쿼리가 10개만 되어도 연산량이 급격하게 많아집니다. 조금 더 효율적으로 구간합을 구할 수 있는 방법 중 하나가 바로 접두사 합(Prefix sum)입니다. 이 때, 접두사 합은 리스트의 맨 앞부터 특정 위치까지 누적 합을 구해 놓은 것을 의미합니다. 즉, 이후의 계산을 위해 일종의 캐싱을 해놓는 것이라 볼 수 있겠습니다. 접두사 합 알고리즘은 다음과 같이 진행됩니다. 1. N개의 수에 대하여 접두사 합(Prefix sum)을 계산하여 배열 P에 저장한다. 2. 매 M개의 쿼리 정보 [L, R]을..