C++의 병합 정렬 트리

정수 배열, 세그먼트 시작 및 끝 포인터 세트, 키 값이 주어지며 여기서 문제 설명은 주어진 범위에서 주어진 키보다 작거나 같은 모든 값을 찾는 것입니다.

예를 들어 이해해 보세요

입력 − arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }

세그먼트 1: 시작 = 2, 끝 = 4, k = 2

세그먼트 2: 시작 = 1, 끝 = 6, k = 3

출력 − 주어진 범위에서 키 값보다 작거나 같은 숫자의 개수는 2 6

설명 − [8, 1, 4]는 2에서 4까지의 범위를 나타내며 2는 범위에서 두 번째로 작은 숫자입니다. [7, 8, 1, 4, 6, 8]은 1부터 6까지의 범위를 나타내며, 6은 범위에서 세 번째로 작은 숫자입니다

Input - arr[] = {2, 7, 9, 4, 6 , 5 , 1 |

단락 1: 시작 위치=3, 끝 위치=6, k=4

단락 2: 시작 위치=2, 끝 위치=5, k=3

Output - 숫자에 주어진 범위에서 키 값보다 작거나 같은 숫자는 다음과 같습니다: 9 7

Explanation - [9, 4, 6, 5]는 3에서 6까지의 범위를 나타내고, 9는 주어진 범위에서 네 번째로 작은 숫자입니다. 숫자 [7, 9, 4, 6]은 2부터 4까지의 범위를 나타내며, 7은 주어진 세그먼트 범위에서 세 번째로 작은 숫자입니다.

다음 프로그램에서 사용된 방법은 다음과 같습니다.

• 정수 배열 선언 유형. 배열의 크기를 계산합니다. 한 쌍의 정수 유형을 형성하는 벡터 유형의 변수를 선언합니다. FOR 루프를 시작하여 배열의 데이터를 벡터로 푸시합니다.

• 주어진 벡터를 정렬하세요. 크기가 MAX인 정수 유형의 벡터 배열을 만듭니다.

• generateTree(1, 0, size - 1, vec, tree) 함수를 호출하고 getSmallestIndex를 queryWrapper(2, 5, 2, size, vec, tree)로 설정합니다.

• 인쇄 입력[getSmallestIndex].

• queryWrapper(1, 6, 4, size, vec, tree) 함수를 호출하도록 getSmallestIndex를 설정합니다.

• generateTree(int treeIndex, int leftIndex, int rightIndex, vector > &a, vector tree[]) 함수 내부에서

  • leftIndex를 rightIndex로 확인한 다음 IF를 확인합니다. 세트 tree[treeIndex].push_back(a[leftIndex].second) 및 return

  • midValue를 (leftIndex + rightIndex) / 2로 설정하고 generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 *를 호출하세요. treeIndex + 1, midValue + 1, rightIndex, a, tree) 및 merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin( ). tree[2 * treeIndex + 1].end(),back_inserter(tree[treeIndex]))

• 함수 내부에서 int 계산KSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int) treeIndex, int key, vector tree[])

  • startIndex를 endIndex로 확인한 다음 tree[treeIndex][0]

  • mid를 (startIndex + endIndex) / 2로 설정하고 last_in_query_range를 (upper_bound(tree[)로 설정합니다. 2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())

  • first_in_query_range를 (lower_bound(tree[2 * treeIndex])로 설정 .begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) 및 M에서 last_in_query_range - first_in_query_range

  • M이 키보다 큰지 확인한 후 반환합니다. 계산KSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)

  • ELSE, 그런 다음 계산KSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree)를 반환합니다. .

• 함수 내부 int queryWrapper(int queryStart, int queryEnd, int key, int n, vector > &a, vectortree[])

  • return CalculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

Example

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){
   if (leftIndex == rightIndex){
      tree[treeIndex].push_back(a[leftIndex].second);
      return;
   }
   int midValue = (leftIndex + rightIndex) / 2;
   generateTree(2 * treeIndex, leftIndex, midValue, a, tree);
   generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);
   merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(),
   tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex]));
}
int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){
      if (startIndex == endIndex){
         return tree[treeIndex][0];
      }
      int mid = (startIndex + endIndex) / 2;
      int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());
      int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(),queryStart) - tree[2 * treeIndex].begin());
      int M = last_in_query_range - first_in_query_range;
      if (M >= key){
         return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);
      }
      else {
         return calculateKSmallest(mid + 1, endIndex, queryStart,queryEnd, 2 * treeIndex + 1, key - M, tree);
      }
}
int queryWrapper(int queryStart, int queryEnd, int key, int n,
   vector<pair<int, int> > &a, vector<int> tree[]){
      return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree);
}
int main(){
   int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 };
   int size = sizeof(input)/sizeof(input[0]);
   vector<pair<int, int> > vec;
   for (int i = 0; i < size; i++) {
      vec.push_back(make_pair(input[i], i));
   }
   sort(vec.begin(), vec.end());
   vector<int> tree[MAX];
   generateTree(1, 0, size - 1, vec, tree);

   cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl;

   int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   return 0;
}

Output

함수 호출을 실행하면 다음과 같은 결과가 출력됩니다. 생성되세요

Count of number which are smaller than or equal to key value in the given range are:
4
6

위 내용은 C++의 병합 정렬 트리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!