구간합

구간의 합을 빠르게 구하고자 할때 Priefix sum을 미리 구해서 답을 도출해냅니다. 누적합이 특정배열에 담기는것으로 상수시간안에 답을 도출해낼 수 있습니다. 10, 20, 30, 40, 50 인 경우 10, 30, 60, 100, 150 으로 누적합 테이블을 생성할 수 있습니다. 이때 left가 1이고 rightrk 3인 구간의 합을 구하는 문제가 주어질 경우 간딴하게 Array[3] - Array[1-1] 의 값으로 답을 결정할 수 있습니다. (식 Array[right] - Array[Left-1]) package test; import java.util.*; public class 구간합알고리즘 { public static void main(String[] args) { // TODO Auto-..