삼성 소프트웨어 (SW) 역량테스트 B형 준비! ① (BST)

문제 https://www.acmicpc.net/problem/2042 풀이 N => 수의 개수, 10^6 M => 업데이트 횟수, 10^4 K => 구간합을 구하는 횟수, 10^4 일반적인 방법으로, 구간합을 구할 떄 마다 배열의 합을 계산할 경우, 한번의 구간합마다 O(N) 이 걸리게 될 것입니다. 이 경우, 최대 K*N = 10^10 이 걸리게 되므로, 문제를 제한시간 내에 풀 수 없습니다. 따라서, 구간합을 구할 때 O(logN) 이하의 알고리즘이 필요합니다. 이를 구현하기 위하여 Segment tree를 아래와 같이 구현합니다. 트리의 Node가 begin~end 까지의 구간합을 갖고 있다고 가정할 때, 왼쪽 Subtree는 begin~1/2*end 오른쪽 Subtree는 1/2*end+1 ~ ..

2019.09.14