Si = Sigma(Aj) (j<=i)라고 정의합시다.

1. S 배열을 어떻게 하면 O(n)에 만들까?

2. S 배열을 통해 어떻게 질문당 O(1)에 답을 낼까?

이 문제들을 해결하면 풀수 있습니다.

오오오!!!!

입력을 받은 후에 모든 경우(시작구간 ~ 종료구간)에 대한 합을 구해 배열에 넣고

시작구간과 종료구간의 범위가 주어질때 그 값이 저장된

배열을 어떻게 찾아가야 되는지 문제를 해결하면 된다는거죠?

제가 잘 이해 한건가요?

{A₁, A₂, ... , A_n}이 있을 때, S_i = A₁ + A₂ + ... + A_i라고 하면,

A_i + A_{i + 1} + ... + A_{j - 1} + A_j는 S_j - S_{i - 1}로 표현할 수 있다는 의미입니다.

아..이해했어요.

그러면 O(n)에 합을 구할수 있고 O(1)에 합을 찾을 수있겟네요.

감사합니다!!

은근히 쉽게 풀렸네요ㅋㅋㅋ

분에 좋은 알고리즘 하나 배웠습니다!

댓글주신 분들 감사합니다.

글쓴분께서는 음수는 어떻게 처리하셨나요?

음수일 경우와 양수일 경우를 따로 구분하지 않으셔도 됩니다.

1~n까지의 합을 sum[n]에 저장한다고 가정해 봅시다.

특정 구간의 합을 계산 하고 싶을시 sum배열을 이용하여

종료지점까지의 구간합에서 시작지점까지의 구간합을 빼주면 됩니다.

예를 들어보면 입력으로  2 -5 4 2 -10 총 5개의 원소가 들어왔을때

합배열은 2 -3 1 3 -7이 나오게 됩니다.

구간 3~5의 합을 구하고 싶으면 합배열 5번째 원소에서(3~5까지의 합) 

합배열의 2번째원소(1~2까지의 합)을 빼주면 됩니다. 

sum[5]-sum[2] = -7 - (-3) = -4로나오게 되며 검산을 해보아도 결과는 같습니다.