문제 https://www.acmicpc.net/problem/5052 풀이 N = 10^5 이기 때문에, O(NlogN) 이하의 알고리즘이 필요합니다. Trie 라는 자료구조는 문자열의 검색 및 업데이트에 최적화 되어있습니다. Trie란? 문자열의 Search Tree 입니다. 위 그림처럼, 단어들의 첫 글자부터 하나씩 depth가 깊어지며 node를 만들기 시작합니다. Trie의 Update 및 Search 등은 Trie의 트리의 높이만큼의 시간뿐이 걸리지 않습니다. (매우빠름) 위 문제에서는, 각 번호들로 Trie 를 만들면서 단어가 끝나는 지점에 표시를 해줍니다. void Node::insert(char* word) { if(word[0] == '\0') { this->isLast = true; ..

문제 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 ~ ..