====== 구간 합 구하기 4 ======

===== 풀이 =====
  * [[ps:구간 쿼리#구간 합|배열의 업데이트 없이 구간 합 쿼리만 들어오는 유형]]이다.
  * [[ps:구간 쿼리#누적 합]]을 O(n)에 만들면, m개의 쿼리를 각각 O(1)에 해결 가능. 총 시간복잡도는 O(n+m)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11659. 구간 합 구하기 4".

- Problem link: https://www.acmicpc.net/problem/11659
- Solution link: http://www.teferi.net/ps/problems/boj/11659
"""

import sys


def main():
    # pylint: disable=unused-variable
    N, M = [int(x) for x in sys.stdin.readline().split()]
    v = 0
    prefix_sum = [v] + [v := v + int(x) for x in sys.stdin.readline().split()]
    for _ in range(M):
        i, j = [int(x) for x in sys.stdin.readline().split()]
        print(prefix_sum[j] - prefix_sum[i - 1])


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}