최근에 세그먼트 트리(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)으로 알려져 있다. 이를 사용한 대표적인 문제로..