## solution  

일반적으로 사용하는 배열의 값을 저장하고, 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클때 사용할수가 없다.  

Prefix sum 방식을 사용하면 O(N) 으로 해결할수 있다.


## CODE  

```python

A,B = list(map(int,input().split()))

nums = list(map(int,input().split()))

for k in range(B):

    idx = list(map(int,input().split()))

    print(sum(nums[idx[0]-1:idx[1]]))

```

이렇게 제출하면 시간초과가 된다는것.   

질문게시판에 따르면 m,i,j가 10만까지이고, 위에 작성한 알고리즘은 O(n^2)라서 시간초과가 된다고 한다.  


```python

A,B = list(map(int,input().split()))

nums = list(map(int,input().split()))

sum_list = []

for idx in range(len(nums)):

    if idx == 0:

        sum_list = [nums[idx]]

    else:

        sum_list += [nums[idx] + sum_list[idx-1]]

for k in range(B):

    idx = list(map(int,input().split()))

    print(sum_list[idx[1]-1] if idx[0]==1 else sum_list[idx[1]-1] - sum_list[idx[0]-2])

```

누적 합의 배열을 만든다. 구간합은 end까지의 누적합에서 start - 1 위치의 누적합을 빼면 만들 수 있다.