업데이트 작업을 사용하여 문자열 범위에서 K번째로 큰 문자를 쿼리합니다.

Fenwick 트리는 BIT(이진 인덱스 트리)라고도 알려진 O(log n) 시간 복잡도로 범위 업데이트 및 범위 검색을 가능하게 하는 데이터 구조입니다.

기본 개념은 문자열의 각 문자에 대한 빈도 배열을 유지하는 것이며, i번째 문자의 빈도는 빈도 배열의 인덱스 i에 기록됩니다. 그런 다음 주파수 배열은 Fenwick Trees를 사용하여 범위 업데이트 및 범위 쿼리를 허용할 수 있습니다.

문제 처리

다음 쿼리를 사용하면 업데이트 범위 [L, R] -

를 사용하여 문자열에서 K번째로 큰 문자를 추출할 수 있습니다.

• 세그먼트 트리 만들기 - 문자열의 각 문자 빈도를 저장하는 세그먼트 트리를 만드는 것부터 시작하세요. 세그먼트 트리의 각 노드는 문자열의 인덱스 범위를 나타내는 범위 내 각 문자의 빈도를 포함하는 빈도 배열을 저장합니다.

• Update - 일부 이전 문자의 빈도를 줄이고 새 문자의 빈도를 늘려 세그먼트 트리에서 일치하는 리프 노드를 업데이트하여 문자열의 문자를 업데이트할 수 있습니다.

  李>

• K번째로 큰 문자 검색 - 세그먼트 트리의 루트에서 시작하여 인덱스 [L, R]의 해당 범위로 재귀적으로 이동하여 해당 범위에서 K번째로 큰 문자를 찾습니다. 범위에서 K번째로 큰 문자는 수정된 이진 검색을 사용하여 각 노드에서 찾을 수 있습니다.

• 시간 복잡도 - O(log n)입니다. 여기서 n은 문자열의 길이입니다. 세그먼트 트리의 공간 복잡도는 O(n)입니다.

문법

문자열이 처음에 제공되고 업데이트될 수 있다고 가정하면 문자열의 간격 [L, R]에서 k번째로 큰 문자를 찾는 쿼리는 다음 구문을 사용할 수 있습니다.

1.초기화 문자열 -

으아악

2. 인덱스에서 문자열 업데이트 -

으아악

3 간격 [P, T] -

에서 k번째로 큰 문자를 찾습니다. 으아악

알고리즘

일부 업데이트를 통해 주어진 간격 [L, R]에서 K번째로 큰 문자를 찾는 알고리즘 -

• 1단계 - 크기가 26인 배열 A를 초기화합니다. 여기서 각 요소 A[i]는 문자열에서 i번째 문자(0부터 인덱스)의 개수를 나타냅니다.

• 2단계 - 문자열 S를 왼쪽에서 오른쪽으로 탐색하고 배열 A의 각 문자 수를 업데이트합니다.

• 3단계 - 업데이트를 처리하려면 A와 동일한 크기의 별도 배열 B를 유지하고 0으로 초기화합니다.

• 4단계 - 업데이트 작업이 수행될 때마다 이전 문자 수와 새 문자 수의 차이를 B의 해당 요소에 추가합니다.

• 5단계 - 간격 [L, R]에서 K번째로 큰 문자를 찾기 위해 인덱스 R까지 A와 B의 누적합을 계산하고 인덱스 L-1까지 A와 B의 누적합을 뺍니다. . 업데이트를 적용한 후 [L, R] 범위의 각 문자 수를 제공합니다.

• 6단계 - [L, R] 범위의 문자를 개수 내림차순으로 정렬합니다.

• 7단계 - K번째 문자를 정렬된 순서로 반환합니다.

따라야 할 방법

방법 1

이 예에서는 문자열 "abacaba"가 초기 문자열로 사용됩니다. 생성자 함수는 문자열의 각 문자 발생 횟수를 계산하여 세그먼트 트리를 초기화합니다. 업데이트 기능은 먼저 이전 문자 수를 줄인 다음 새 문자 수를 늘려 문자열과 세그먼트 트리를 업데이트합니다. 쿼리 함수는 이진 검색을 사용하여 [L,R]에서 k번째로 큰 문자를 반환합니다.

예 1

으아악

출력

으아악

방법 2

프로그램은 먼저 N x 26 크기의 2차원 배열 freq를 초기화합니다. 여기서 freq[i][j]는 문자열 s의 접두사에서 j번째 문자부터 i번째 인덱스까지의 빈도를 나타냅니다. 그런 다음 각 인덱스 i에 대해 i번째 인덱스의 문자 수를 늘리고 모든 이전 문자 수를 추가하여 freq 배열을 업데이트합니다.

주파수 배열을 초기화한 후 두 가지 쿼리를 실행합니다. 각 쿼리에서는 인덱스 R의 문자 수에서 인덱스 L-1 이전의 문자 수를 빼서 [L, R] 범위의 문자 수를 계산합니다. 그런 다음 지금까지 본 문자 수를 추적하면서 0에서 25까지 문자 빈도를 반복합니다. K번째로 큰 문자에 도달하면 해당 인덱스를 저장하고 루프에서 벗어납니다. 마지막으로 저장된 인덱스에 해당하는 문자를 인쇄합니다.

쿼리 사이에서 인덱스 4의 문자를 "a"로 변경하여 문자열을 업데이트합니다. 주파수 배열을 효율적으로 업데이트하기 위해 해당 인덱스에서 이전 문자와 새 문자의 개수를 업데이트한 다음 업데이트된 접두사 합계를 사용하여 모든 후속 문자의 개수를 다시 계산합니다.

예 1

으아악

출력

으아악

결론

마지막으로 간격 [L, R]에서 K번째로 큰 문자를 업데이트로 식별하라는 요청은 선분 트리와 이진 검색 방법의 조합을 사용하여 효율적으로 해결할 수 있습니다. 이진 검색 기술은 범위에서 K번째로 큰 문자를 찾는 데 사용되며, 선분 트리는 범위에서 문자 발생 빈도를 추적하는 데 사용됩니다.

위 내용은 업데이트 작업을 사용하여 문자열 범위에서 K번째로 큰 문자를 쿼리합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!