구간 합
구간 합의 핵심 이론
구간 합 알고리즘을 활용하려면 합 배열을 구해야 한다
//합 배열 S 정의
S[i]=A[0]+A[1]+A[2]+...+A[i-1]+A[i]
//합 배열 S를 만드는 공식
S[i]=S[i-1]+A[i]합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다. 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 줄어든다.
구간 합 알고리즘을 활용하려면 합 배열을 구해야 한다
//합 배열 S 정의
S[i]=A[0]+A[1]+A[2]+...+A[i-1]+A[i]
//합 배열 S를 만드는 공식
S[i]=S[i-1]+A[i]합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다. 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 줄어든다.