최근에 세그먼트 트리(Segment Tree)를 접해보았다. 학부 수업에서 다루지 않은 자료구조이기에 이해하는 데 어려웠다. 그래서 그런지 관련된 BOJ 문제의 난이도는 solved.ac 기준으로 거의 Gold I 이상이었다. 최근에 생긴 BOJ Book에서 세그먼트 트리에 관한 내용을 보았는데, 특히 solved.ac CLASS 6에서도 이와 관련된 문제가 있었다.
세그먼트 트리
누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다.
book.acmicpc.net
세그먼트 트리의 시간 복잡도는 O(lgN)으로 알려져 있다. 이를 사용한 대표적인 문제로 구간 합 문제가 있다. 필자에게는 아직 생소한 개념이라서 세그먼트 트리의 구현도 어려웠다. 시간이 된다면 세그먼트 트리에 대하여 공부하려고 한다. 앞으로도 다양한 자료구조와 알고리즘을 공부해서 코딩 실력을 키우고 싶다.