매번 합을 구하는 방식으로는 시간 내에 해결하기가 어려울 것 같습니다.

안녕하세요! 우선 시간복잡도가 O(WN)이어서 시간초과가 나는 것 같습니다. Prefix sum으로 O(N)만에 합을 미리 구하면 a에서 b 사이의 합은 O(1)만에 구할 수 있습니다. 그리고 이중 루프에서 변수 j를 재사용하는것도 문제가 되는 것 같아요. 

위와 같은 단순한 코드도 10억 번을 반복하면 생각보다 제법 오랜 시간이 필요합니다. (제 컴퓨터에서는 2.5~3.5초 정도 걸리네요)

문제에서 데이터(N)가 최대 10만개, 질의(M)의 수가 최대 10만개라고 했고.. 최악의 경우 매 질의마다 배열 전체 범위 (0~99999)가 입력될 수도 있기때문에

작성하신 솔루션의 경우, M개의 질의마다 N번의 덧셈을 수행하기 때문에 일지매님이 언급해주신 Big-O표기법으로 시간복잡도를 표현하면 O(MN)이 됩니다.

단순히 10억번(10^9)의 덧셈을 수행하는데 3초 정도가 걸리는데, MN번(10^10)의 덧셈을 수행하는데는 더 많은 시간이 걸리겠죠.

또, 상수시간( O(1) )의 연산도 단순한 연산이 아닌 조금 더 시간이 필요한 연산(곱셉, 나눗셈, 함수호출..)이 있을수도 있고, 연산 자체가 많이 포함되어 있을수도 있습니다.