구간 합 알고리즘

합배열

정의

:  기존의 배열을 전처리한 배열

S[i] = A[0]  + A[1]   + A[2]   + A[3] + ··· + A[i-1]   + A[i]

 

시간 복잡도

: O(1)

- 합 배열을 미리 구해두면 구간 합을 O(1)의 시간복잡도로 계산할 수 있다.

 

공식

S[i] = S[i-1] + A[i]

class PrefixSum{
    private long[] sum;
    
   	//생성자
    PrefixSum(int[] arr){
    	sum = new long[arr.length];
        sum[0] = arr[0]; 
        for(int i = 1; i < arr.length; i++){
            sum[i] = sum[i-1] + arr[i];
        }
    }
}

 

필요성

: 합배열을 미리 구해놓으면 구간합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

=> 합 배열 미리 구해두면 구간 합은 한 번의 계산으로 구할 수 있다.

/*

합배열 없이 구간합 구하는 경우

- A[i]부터 A[j]까지 배열 합 구하기

최악의 경우: i = 0, j = N => 시간복잡도: O(N)

*/

 

구간 합

공식

: i~j까지 구간 합

S[j] - S[i - 1]

class PrefixSum{
    private long[] sum;
    
   	//생성자
    PrefixSum(int[] arr){
    	sum = new long[arr.length];
        sum[0] = arr[0]; 
        for(int i = 1; i < arr.length; i++){
            sum[i] = sum[i-1] + arr[i];
        }
    }
    
    //필요한 구간합 반환
    //s: 시작 인덱스, e: 끝 인덱스
    public long prefixSum(int s, int e){
    	//처음부터 시작하는 구간합
    	if(s == 0)
        	return sum[e];
            
        //특정 인덱스부터 시작하는 구간합
        return sum[e] - sum[s - 1];
    }
}

 

예시

: 인덱스 2~5까지의 구간 합

S[5] = A[0]  + A[1]   + A[2]   + A[3] + A[4] + A[5]

S[1] = A[0]  + A[1]

구간 합 = S[5] - S[1] = A[2]   + A[3] + A[4] + A[5]   => O(1)