합 배열 생성 공식
S[i] = S[i - 1] + A[i]
예를 들어 원본 배열
1 2 3 4 5
합배열은
1 3 6 10 15
가 됨
1
3 = 1+2
6 = 1+2+3 = 3(-1인덱스)+3
헷갈리는 지점이 여기
그럼 S[i - 1] 에서 i가 0이면 -1인덱스라는게 말이 되냐!
-> 그래서 i를 1부터 시작해줍니다.. 합배열을 만들기 위한 for문이니까
대신
1. S[0]은 0으로 선언하기 -> -1인덱스라는 건 없으니깐
2. A[i]에서 원래 0부터 시작했어야 하는거였으니 A[i - 1] 이라고 하면
S[0] = 0
S[1] = S[0] + A[0] = 0 + 1 = 1
S[2] = S[1] + A[1] = 1 + 2 = 3
S[3] = S[2] + A[2] = 3 + 3 = 6
이렇게 기준을 맞춰줬죠? 왜 순서기준 (1부터 시작)으로 맞추냐! -> 1번째부터 3번째까지의 부분 합, 2번째부터 4번째까지의 부분 합
이럴 때 1 -1 = 0번째 인덱스, 3 - 1 = 2번째 인덱스
이렇게 일일히 -1하여 생각해야한다는거
그치만 원본 배열보다 1만큼 더 큰 합 배열을 만들어놓으면 부분 합 구하기 공식에 바로 1, 3을 적용할 수 있다는거임
S[j] - S[i - 1]
S[3] - S[1 - 1] 이렇게 요구하는 순서번호를 가공할 필요 없이 그냥 적용하면 댐
-> 애초에 쉽게 구간 합을 구하려고 합배열 공식이 나온것이고 이걸 편하게 사용하기 위해 합배열의 인덱스를 조정했다...이 너낌
!! 인덱스와 순서번호를 헷갈리지 말자!!
int[] s = new int[arr.length + 1];
s[0] = 0;
for (int k = 1; k <= n; k++) {
s[k] = s[k - 1] + Integer.parseInt(arr[k - 1]);
}(백준 11659 코드 일부분)
합배열 사용 이유
배열 길이 n, 쿼리 갯수 m (실행해야할 작업 개수)
사용 안할 때 : O(n * m)
사용할 때 O(n)+O(n + m)
