Prefix Sum

개요

수열 이 주어지면 번째 항 부터 번째 항 까지의 합을 빠르게 구하기 위해 사용하는 다이나믹 프로그래밍 알고리즘입니다.

번째 항부터 번째 항 까지의 합을 이라 합시다. 그렇다면 우리는 라는 점화식을 얻을 수 있습니다. DP를 통해 을 전처리하면 에 번째 항 부터 번째 항 까지의 합 을 구할 수 있습니다.
전처리 시간 복잡도는 입니다.

문제