트리 배열(오프라인 쿼리)을 사용하여 L~R 범위에서 K보다 큰 요소 수를 계산합니다.

컴퓨터 과학 분야에서는 쿼리 선택 및 업데이트 작업이 포함된 대규모 데이터 세트를 처리해야 합니다. 낮은 시간 복잡성으로 이러한 작업을 실시간으로 수행하는 것은 개발자에게 어려운 작업입니다.

펜윅 트리를 사용하는 것은 이러한 범위 기반 쿼리 문제를 해결하는 효과적인 방법입니다.

Fenwick Tree는 요소를 효율적으로 업데이트하고 테이블에 있는 숫자의 접두어 합계를 계산할 수 있는 데이터 구조입니다. 이진 인덱스 트리라고도 합니다.

이 기사에서는 Fenwick 트리를 사용하여 L에서 R까지의 범위에서 K보다 큰 요소 수를 찾는 방법에 대해 설명합니다.

입력 및 출력 시나리오

N개의 요소가 있는 배열이 있고 L에서 R까지의 범위에서 K보다 큰 배열의 요소 수를 찾고 싶다고 가정합니다.

으아아아

오프라인 쿼리란 무엇인가요?

오프라인 쿼리는 미리 정해진 데이터 세트에 대해 수행되는 쿼리 작업입니다. 즉, 이러한 작업은 쿼리를 처리하는 동안 추가로 수정되지 않는 데이터 세트에서만 수행됩니다.

펜윅 트리 사용하기

여기서는 배열의 모든 요소를 ​​순서대로 포함하는 각 노드에 대한 벡터를 갖는 Fenwick 트리를 사용합니다. 그런 다음 이진 검색을 사용하여 각 쿼리에 응답하고 요소 수를 계산합니다.

• BIT에서 접두어 합계를 각각 업데이트하고 검색하기 위해 updateTree() 및 total()이라는 두 개의 함수를 만듭니다.

• 다음으로, L부터 R까지의 범위에서 "K"보다 큰 요소를 계산하는 또 다른 함수를 만듭니다. 이 함수는 "arr", "N", "L", "R" 및 "K" 입력 값을 허용합니다.

• 카운트는 최대 범위 N의 누적 합계에서 K의 누적 합계를 빼서 계산됩니다.

범위를 벗어난 요소를 제외하려면 L-1의 누적합을 뺍니다(L이 1보다 큰 경우).

예

으아아아

출력

으아아아

대체 방법

여기서 쿼리를 저장할 별도의 벡터를 생성하겠습니다. 각 쿼리는 index 및 val이라는 두 개의 변수로 구성됩니다. index 는 배열의 위치를 ​​저장하는 데 사용되고, val은 해당 인덱스의 요소 값을 저장하는 데 사용됩니다. 이 접근 방식을 통해 개발자는 다양한 쿼리 작업을 수행할 수 있습니다. 또한 BIT를 사용하여 각 쿼리에 대해 K 보다 큰 요소 수를 계산합니다.

예

으아아아

출력

으아아아

결론

각 쿼리에 대한 답을 찾기 위해 인덱스 L에서 R까지 배열을 반복하고 배열 요소가 K보다 클 때마다 1을 추가하면 됩니다. 그러나 시간 복잡도를 줄이기 위해 펜윅 트리를 사용하여 이러한 쿼리 작업을 수행합니다. Fenwick 트리 대신 Line Segment Tree 및 Sparse Table을 사용하여 이러한 쿼리 작업을 수행할 수도 있습니다.

위 내용은 트리 배열(오프라인 쿼리)을 사용하여 L~R 범위에서 K보다 큰 요소 수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!