查询子数组中不同元素的数量 在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