구간의 합을 빠르게 구하고자 할때 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-generated method stub
int n = 5;
int[] data = {10, 20, 30, 40, 50};
ArrayList<Integer> al = new ArrayList<>();
int sum = 0;
al.add(sum);
for(int i=0; i<data.length; i++) {
al.add(sum+=data[i]);
}
int left = 2;
int right = 3;
System.out.println(al.get(right)-al.get(left-1));
}
}
*ref : 동빈나 유튜브