[BOJ] 2042번: 구간 합 구하기

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

만약 D[i] = num[1]+num[2]+...+num[i]라고 두고, b번째 수부터 c번째 수의 합을 D[c] - D[b-1]로 구하려고 한다면 합은 상수시간에 구할 수 있지만 a번째 수를 변경할 때 D[a]~D[N]의 값을 전부 바꿔야하기 때문에 시간내로 풀 수 없습니다.

즉 합도 O(logN)로 구하고 a번째 수의 변경도 O(logN)으로 구할 수 있으면 제일 좋을텐데 전형적인 세그먼트트리 혹은 Binary Index Tree로 풀 수 있는 문제입니다. Binary Indexed Tree는 http://blog.secmem.org/486 에 상세히 잘 나와있습니다.

https://github.com/encrypted-def/BOJ/blob/master/2042.cpp