Segment Tree 응용 (1) - 응용의 기초, Segment Tree 활용 팁

Segment Tree의 활용성은 무궁무진하다. 정말 중요한 자료구조(알고리즘)이며, 대회에도 다양한 형태로 정말 많이 출제가 되어진다. 우리는 거의 모두 Segment Tree를 처음 배우는 과정에서 배열의 값이 바뀌어도 구간합을 빠르게 구할 수 있는 자료구조로서 Segment Tree를 배우지만, 이를 어떻게 추가적으로 활용하느냐, 노드에 어떤 다양한 값을 담느냐에 따라서 정말 다양한 연산을 처리할 수 있다.

Segment Tree는 어떨 때 사용할까? 우리가 풀이에 세그먼트 트리를 고려해 볼 수 있는 상황은 간단하게 생각하면 두가지 정도 있다. 첫번째로 쿼리 형식으로 문제가 주어졌을 때이고, 두번째로 시간복잡도를 log로 만들고 싶을 때이다. log가 나오게 된다면 어떤 문제이던지 간에 한번쯤은 생각을 해보고 넘어가야 할 것이다. dp,기하,odc 등 수많은 곳에 섞여서 쓰일 여지가 있기 때문이다. 

Segment Tree 응용은 크게 두가지로 나눌 수 있다.
1. 구간합 최대, 가장 큰 원소, 구간 내 숫자를 그냥 쭉 나열 한 값 등 세그먼트 트리의 노드에 변화를 취해서 세그먼트 트리 자체에서 얻는 값이 평범한 구간 합이 아닌경우.
2. inversion counting, 세그에서 이분 탐색 등 세그먼트 트리에서 얻는 값을 활용하여 다른 값을 구하는 경우.

그래서 항상 Segment Tree를 쓸 때는 어떠한 최종 목표, 답을 구하기 위해서 Segment Tree를 어떤 식으로, 어디까지 1번으로 활용할 지, 이를 이용하여 답을 얻기까지 2번 과정을 어떤식으로 해나갈지를 생각하면 좋다.

앞으로 Segment Tree의 응용 관련 포스팅에서는 2번 관련해서는 유명한 inversion counting, 3-types 정도만 다룰 것이고, 1번위주로 포스팅을 작성하려고 한다.