문제를 풀기 전에 우선 구간합을 구하는 방법을 알아야한다. 하지만 또! 구간합을 구하기 전에 합 배열을 만들줄 알아야 한다. ㅎㅎ 알아야하는 이유는 다음과 같다. 반복문으로 해당 문제를 풀었을때에는 시간 초과가 발생했다. 주어진 질의의 개수가 최대 10만개이다. 수의 개수도 최대 10만개이다. 최악의 경우에는 10만개의 수를 가진 배열안에서 10만번의 질의를 반복문을 돌려야한다. 이때 반복문을 통한 시간복잡도 O(n^2)로는 해결할 수 없다. 이 때 구간합으로 문제를 해결한다면 누적배열합을 생성하는데 O(N)이 들고 M번 반복하므로 O(N+M)의 시간복잡도를 갖는다. 해당 문제는 1초안에 풀어야하는데 구간합 알고리즘을 모른다면 반복문으로 통해 최악의경우 1억회이상의 연산을 하기때문에 시간내에 풀기 힘들것..