C++에서 주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리

<시간/>

이 문제에서 배열 arr[] 및 Q 쿼리가 제공되며 각각은 두 가지 유형 중 하나일 수 있습니다.

{1, L, R}- [L, R] 범위의 배열 요소 수입니다.
{2, index, val}− 인덱스의 요소를 val로 업데이트하기 위한 것입니다.

우리의 임무는 C++에서 주어진 범위의 값을 가진 배열 요소의 개수에 대한 쿼리를 해결하는 프로그램을 만드는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :arr[] ={1, 5, 2, 4, 2, 2, 3, 1, 3}

Q =3

쿼리 ={ {1, 4, 8},

{2, 6, 5},

{1, 1, 4}}

출력 :3 7

설명

쿼리 1:[4, 8] 범위의 배열 요소 수를 계산합니다. 개수 =1

쿼리 2:업데이트 요소 arr[6] =5. 새 배열, arr[] ={1, 5, 2, 4, 2, 2, 5, 1,3}

쿼리 1:[4, 8] 범위의 배열 요소 수를 계산합니다. 개수 =7

해결 방법

문제에 대한 간단한 해결책은 배열을 직접 탐색하고 범위, 즉 L =에 있는 모든 요소를 찾는 것입니다.

예

#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
   int ValueCount = 0;
   for (int i = 0; i < N; i++) {
      if (arr[i] >= L && arr[i] <= R) {
         ValueCount++;
      }
   }
   return ValueCount;
}
int main() {
   int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   int Q = 3;
   int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
   for(int i = 0; i < Q; i++){
      if(query[i][0] == 1)
         cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
      else if(query[i][0] == 2){
         cout<<"Updating Value \n";
         arr[query[i][1]] = query[i][2];
      }
   }
   return 0;
}

출력

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7

모든 루프에 대해 한 번 반복 접근하는 솔루션입니다. 따라서 시간 복잡도는 O(Q*N) 차수입니다.

문제를 해결하기 위한 더 나은 접근 방식은 Binary IndexedTree 또는 Fenwick Tree 데이터 구조를 사용할 수 있습니다. 여기에서 배열 요소를 트리에 저장하여 배열 요소를 인덱스로 사용할 수 있습니다. 그리고 데이터 구조에 대해 내장된 getSumfunction을 사용하여 범위 요소의 개수를 쉽게 찾을 수 있습니다.

요소 수[L, R] =getSum(R) - getSum(L - 1)

예

#include <iostream>
using namespace std;
class BinaryIndTree {
   public:
      int* BIT;
      int N;
      BinaryIndTree(int N) {
         this->N = N;
         BIT = new int[N];
         for (int i = 0; i < N; i++) {
            BIT[i] = 0;
         }
      }
      void update(int index, int increment) {
      while (index < N) {
         BIT[index] += increment;
         index += (index & -index);
      }
   }
   int calcSum(int index) {
      int sum = 0;
      while (index > 0) {
         sum += BIT[index];
         index -= (index & -index);
      }
      return sum;
   }
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree*fenwickTree){
   int removedElement = arr[index];
   fenwickTree->update(removedElement, -1);
   arr[index] = val;
   fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree*
fenwickTree) {
   return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
   int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 3;
   int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
   int N = 100001;
   BinaryIndTree* fenwickTree = new BinaryIndTree(N);
   for (int i = 0; i < n; i++)
      fenwickTree->update(arr[i], 1);
   for(int i = 0; i < Q; i++){
      if(query[i][0] == 1)
         cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2],fenwickTree)<<endl;
         else if(query[i][0] == 2){
         cout<<"Updating Value \n";
         UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
      }
   }
   return 0;
}

출력

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7