[개념정리] 구간 합

[YubinShin]

구간 합 이란?

구간 합은 합 배열을 이용하여 시간복잡도를 줄이기 위해 사용하는 알고리즘입니다.

시간복잡도

O(N)

합 배열

기존의 배열을 누적 합해서 전처리한 배열.

스트림 방식 보다 전통적인 반복문이 더 좋다고 한다.
반복문의 i 를 1부터 시작하면 편리하다.

int[] 원본배열 = {1, 2, 3, 4, 5}; 
int[] 누적합 = new int[원본배열.length];
  
for(int i = 1; i < 원본배열.length; i++){
  누적합[i] = 누적합[i-1] + 원본배열[i];
}

구간 합 구하는 법

누적합[ j ] - 누적합[ i - 1 ]

2번째 부터 5번째 요소까지의 합을 구하고 싶어

// 누적합 = {1, 3, 6, 10, 15}
// 누적합[5] - 누적합[2 - 1]
// 15 - 1 = 14

만약 배열 내 요소가 자주 바뀌어서 합배열이 무용지물이면 어떡하지?

이후 나오는 세그먼트 트리로 풀이 가능!