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] 범위에서 두 번째로 작은 수이고 6은 1에서 6까지의 범위를 나타냅니다. 범위에서 가장 작은 숫자

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

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

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

출력 − 주어진 범위에서 키 값보다 작거나 같은 숫자의 개수는 다음과 같습니다. 9 7

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

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

정수형 배열을 선언합니다. 배열의 크기를 계산합니다. 정수형 쌍을 이루는 벡터형 변수를 선언합니다. 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를 설정합니다.
함수 내부에서 void generateTree(int treeIndex, int leftIndex, int rightIndex, vector> &a, vector tree[])
- IF leftIndex를 rightIndex로 확인한 다음 settree[treeIndex].push_back(a[leftIndex].second) 및 반환
- 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 computeKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[])
- IF 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이 키보다 큰지 확인한 다음 계산을 반환하십시오.
- ELSE, 그런 다음 computeKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree)를 반환합니다.
int queryWrapper(int queryStart, int queryEnd, int key, int n, vector> &a, vectortree[])
함수 내부
- countKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, 키, 트리) 함수에 대한 반환 호출

예시

#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;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

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