제목에서 알 수 있듯이, 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 >= 10,000 이상의 입력이 들어온다면, O(N^2)의 dp 알고리즘으로는 풀 수 없으므로, O(N log N) 의 풀이를 알아야 한다. 그리고 우리는 세그먼트 트리를 활용한 구간 최댓값을 구하는 것으로 이를 풀 수 있다. 예제를 예로 들겠다. 배열 요소가 저장된 배열을 S라 할 때, S는 다음과 같이 표현된다. S 9 5 4 6 1 3..