Red Salmon

출처 : https://www.acmicpc.net/problem/11441

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.01/11441.cpp

이 문제의 풀이는 이미 내가 과거에 풀어본 배열내 구간 계산이므로 세그먼트 트리를 적용시키면 된다. 설마 이 문제를 읽고 구간 a부터 b까지의 합을 계속 더하고 더하고 하는 사람은 없을것이다. 무조건 TL이 나올것이다.

세그먼트 트리도 정답이지만 이 문제는 조금 더 생각하면 다른 해법도 있다.

어차피 구간내의 합이기 때문에 0부터 계속 더해나가는 것이다. 즉

a[0]=a[0]

a[1]=a[1]+a[0]

a[2]=a[2]+[1]

a[3]=a[3]+a[2]

이렇게 하면 구간 0부터 n까지의 합이 계속 저장이 된다. 그리고 입력으로 구간이 입력이 되면 그 구간을 빼주면 된다.

즉 a~b구간의 합은 0~b구간의 합에서 0~a구간의 합을 뺀다면 a~b구간의 합이 되는것이다. 이렇게 푸는것도 간단히 푸는 방법이다.

그러나 나는 세그먼트트리 연습겸 저렇게 풀어봤다.

이런 문제가 참 괜찮은 문제라고 생각한다.