[BaekJoon] 백준 11659번 : 구간 합 구하기 4

11659번 : 구간 합 구하기 4

구간합을 구할땐 prefix_sum 을 이용하면 된다.

한 번 구간합을 구해두면 O(1) 시간에 답을 구할 수 있다.

---

import sys


def solution():
    N, M = map(int, sys.stdin.readline().rsplit())
    arr = list(map(int, sys.stdin.readline().rsplit()))
    prefix_sum = [0]
    for i in range(1, N + 1):
        prefix_sum.append(prefix_sum[i - 1] + arr[i - 1])

    for _ in range(M):
        start, end = map(int, sys.stdin.readline().rsplit())
        print(prefix_sum[end] - prefix_sum[start - 1])


if __name__ == "__main__":
    solution()