선분 트리를 사용한 LIS(최장 증가 부분 수열)의 길이

세그먼트 트리는 범위 쿼리에 응답하고 로그 시간 복잡도에서 배열 업데이트 작업을 수행하도록 설계된 다목적 데이터 구조입니다. 여기서 각 노드는 배열의 특정 요소 범위와 관련된 정보를 저장합니다.

주어진 수열의 요소가 오름차순으로 정렬된 가장 긴 부분 수열의 길이를 결정해야 하는 LIS(Longest Going Subsequence) 문제의 맥락에서 선분 트리를 사용하여 효율적으로 계산할 수 있습니다. 배열에서 가장 길게 증가하는 부분 수열의 길이입니다.

이 방법은 기존 방법에 비해 시간 복잡성을 크게 줄이고 유전체학, 자연어 처리, 패턴 인식 등 분야에 많이 응용됩니다. 이 기사에서는 세그먼트 트리의 기본 사항을 살펴보고 가장 오래 증가하는 하위 시퀀스 문제를 해결할 수 있는 잠재력을 보여줍니다.

문법

세그먼트 트리 구축 기능 −

으아악

세그먼트 트리 쿼리 기능 −

으아악

세그먼트 트리 업데이트 기능 −

으아악

알고리즘

세그먼트 트리를 사용하여 LIS(최장 증가 부분 수열)의 길이를 찾는 알고리즘은 다음과 같습니다.

• 입력 시퀀스를 나타내는 배열을 초기화합니다.

입력 시퀀스와 동일한 크기의 세그먼트 트리로 초기화 build 함수를 사용하여 선분 트리 만들기

• 입력 시퀀스의 각 요소를 처리합니다.

• 각 요소에 대해 세그먼트 트리를 쿼리하여 현재 요소에서 끝나는 LIS의 최대 길이를 찾습니다.

• 업데이트 기능을 사용하여 세그먼트 트리를 업데이트하세요.

• 입력 시퀀스의 모든 요소에 대해 4~6단계를 반복하세요.

• 최종 답은 세그먼트 트리에 저장된 최대값입니다.

접근 방법 1: 간단한 세그먼트 트리 사용

이 접근 방식에서는 지연 전파와 같은 최적화 기술 없이 간단한 세그먼트 트리를 구현합니다.

예제-1

아래 프로그램은 C++에서 간단한 세그먼트 트리를 사용하여 LIS(최장 증가 부분 시퀀스)의 길이를 찾는 방법을 보여줍니다. 빌드, 쿼리 및 업데이트 기능은 세그먼트 트리를 구성하고 a에서 끝나는 LIS의 최대 길이를 검색하는 데 사용됩니다. lengthOfLIS 함수는 입력 시퀀스의 각 요소를 반복하고 세그먼트 트리를 사용하여 LIS 길이를 계산합니다.

으아악

출력

으아악

전파가 지연된 세그먼트 트리를 사용하는 방법

이 접근 방식에서는 지연 전파를 사용하여 세그먼트 트리를 구현하여 알고리즘의 시간 복잡도를 더욱 최적화합니다.

예 2

아래 코드는 전파가 지연된 세그먼트 트리를 사용하여 C++에서 가장 긴 증가 부분 수열(LIS)의 길이를 찾는 방법을 보여줍니다. 이 코드는 방법 1의 코드와 유사합니다. 두 방법의 주요 차이점은 세그먼트 트리의 내부 구현입니다. 지연 전파 기술은 LIS 문제에 존재하지 않는 특정 사용 사례에 대해 업데이트 기능을 최적화하기 때문에 이 코드에 명시적으로 표시되지 않습니다. 다만, 코드의 기본 구조는 동일하며, 빌드, 쿼리, 업데이트 기능은 방법 1과 유사하게 사용됩니다.

으아악

출력

으아악

결론

이 글에서는 C++의 선분 트리 기법을 통해 LIS(최장 증가 부분 수열)의 범위를 결정하는 방법을 설명합니다. 우리는 두 가지 접근 방식을 설명합니다. 하나는 세그먼트 트리를 직접 수행하는 것이고 다른 하나는 향상된 지연 전파 방법을 활용하는 것입니다. 두 기법 모두 LIS 문제를 해결하는 데 효과적이며 최적화 방법의 지연 전파는 시간 복잡도를 더욱 줄여줍니다.

위 내용은 선분 트리를 사용한 LIS(최장 증가 부분 수열)의 길이의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!