查询子数组中不同元素的数量 在C ++中设置2

在这个问题中，我们得到了一个大小为n的数组arr []，并且得到了一个查询。每个查询包含两个值(L,R)。我们的任务是创建一个程序来解决子数组中不同元素数量的查询

问题描述-在这里，我们需要找到从索引(L-1)到(R-1)子数组中存在的不同整数的总数。

让我们举个例子来了解这个问题，

输入值

arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]

输出结果

4

说明

对于查询1：L = 1和R = 4，我们需要找到从索引0到3的不同元素的数量，即4。

对于查询2：L = 2＆R = 6，我们需要找到从索引1到5的不同元素的数量，即3。

解决方法

解决每个查询的一种简单方法是将数组从L遍历到R并将元素存储到集合中，其大小将给出查询结果。我们在上一组讨论过的相同。

解决该问题的更有效方法是使用段树数据结构。它将存储给定范围内的不同元素计数。

段树是一种特殊的树，以段的形式存储信息。

段树的叶节点表示数组的元素。非叶节点表示具有所需值的段。在这里，它将存储不同的元素。对于此数据结构的实现，我们将使用Set。

实施上述解决方案的程序-

示例

#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;

void CreateSegmentTree(int i, int s, int e, int arr[]) {

   if (s == e) {
      segmentTree[i].insert(arr[s]);
      return;
   }
   CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
   CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
   segmentTree[i].insert( segmentTree[2 * i].begin(), segmentTree[2 * i].end());
   segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}

set<int> findDistSubarray(int node, int l, int r, int a, int b) {

   set<int> left, right, distinctSubarray;
   if (b < l || a > r)
   return distinctSubarray;
   if (a <= l && r <= b)
   return segmentTree[node];
   left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
   distinctSubarray.insert(left.begin(), left.end());
   right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
   return distinctSubarray;
}

int main() {

   int arr[] = {4, 6, 1, 3, 1, 6, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int query[] = {1, 4};
   int i = (int)ceil(log2(n));
   i = (2 * (pow(2, i))) - 1;
   segmentTree = new set<int>[i];
   CreateSegmentTree(1, 0, n - 1, arr);
   set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
   cout<<"The number of distinct elements in the subarray is "<<distCount.size();
   return 0;
}

输出结果

The number of distinct elements in the subarray is 4