구간 합 구하기 4

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

"""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()