[2018 study] 부분합 및 세그먼트 트리

부분합

특정 구간 상의 합을 구할 때 필요한 구간의 합을 구하게 되는 경우 일일이 for문을 계산하기 때문에 10만이 넘는 경우 계산을 하는 시간이 많아져 많은 연산으로 인한 timeover가 발생할 수 있다.

이를 해결하기 위해 사용하는 방법으로는 input 값이 들어올때 바로바로 계산을 해서 저장을 하게 되면 이 문제는 해결이 된다.

input	12	3	2	4	2	1	5	1
sum	12	15	17	21	23	24	29	30

이때 2~5번까지 의 sum을 구하기 위해서는 단 1번의 연산만 시행을 하면 된다. 5번 합 - 1번 합 = 11

단 1번의 계산으로 성립이 되기 때문에 0(1)로 성립이 가능하다.

구간의 합이 0에 가까운 구간을 찾기 위해서는 구간 합의 변화가 0에 가까운 것을 찾으면 된다.

세그먼트 트리

https://www.acmicpc.net/blog/view/26

http://www.crocus.co.kr/658?category=150836