<aside> 📌

제가 작성한 이 글을 참조해 주세요. (이 글이 원본)

</aside>

제목에서 알 수 있듯이, LIS 문제를 $O(N log N)$ 의 시간복잡도로 세그먼트 트리를 이용하여 풀 수 있다.

예제로

9
9 5 4 6 1 3 7 10 2

라는 입력이 주어진다고 해보자. 여기서 $LIS$ 는 무엇일까?

$LIS = \{ 5, 6, 7, 10 \}$, 혹은 $\{ 4, 6, 7, 10 \}$, 혹은 $\{ 1, 3, 7, 10 \}$ 등으로, 길이는 $4$ 이다.

우리는 만약에 $N \ge 10,000$ 이상의 입력이 들어온다면, $O(N^2)$ 의 dp 알고리즘으로는 풀 수 없으므로, $O(N log N)$ 의 풀이를 알아야 한다.

그리고 우리는 세그먼트 트리를 활용한 구간 최댓값을 구하는 것으로 이를 풀 수 있다.

예제를 예로 들겠다. 배열 요소가 저장된 배열을 $S$ 라 할 때, $S$ 는 다음과 같이 표현된다.