구간 합의 핵심 이론 합 배열 S의 정의 S[i]=A[0]+A[1]+A[2]+...+A[i-1]+A[i] #A[0]부터 A[i]까지의 합 합배열: 기존의 리스트 데이터를 전처리한 배열 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복ㅈ갑도가 O(N)에서 O(1)로 감소 리스트A: 15, 13, 10, 7, 3, 12 합 배열S: 15, 28, 38, 45, 48, 60 A[i]부터 A[j]까지의 리스트 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우 ->시간 복잡도 O(N) #합 배열 S를 만드는 공식 S[i]=S[i-1]+A[i] #구간 합을 구하는 공식 S[j]-S[i-1] 원리: 합 배열만 미리 구해두면 구간 합은 한 번의 계산으로 구할 수 있..