2042 구간 합 구하기

기본적인 배열을 통한 누적합은 구간합을 구하는 데 O(1)의 짧은 시간복잡도가 걸리지만 값이 변경됐을 때는 최대 N번을 통해 변경을 해야므로, 변경을 한 후 누적합을 구하는 시간복잡도는 O(N)이라고 할 수 있다. 하지만 세그먼트 트리를 구하면 O(lgN)만에 연산을 끝낼 수 있다

 

문제: https://www.acmicpc.net/problem/2042

깃허브주소: https://github.com/surinoel/boj/blob/master/2042.cpp