# 數組范圍查詢以搜索元素 > 原文： [https://www.geeksforgeeks.org/array-range-queries-for-searching-an-element/](https://www.geeksforgeeks.org/array-range-queries-for-searching-an-element/) 給定一個由`N`個元素組成的數組和形式為`L R X`的`Q`個查詢。對于每個查詢，必須輸出元素`X`是否存在于索引`L`和`R`（包括）之間的數組中。 **先決條件**： [Mo 的算法](https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/) **示例**： ``` Input : N = 5 arr = [1, 1, 5, 4, 5] Q = 3 1 3 2 2 5 1 3 5 5 Output : No Yes Yes Explanation : For the first query, 2 does not exist between the indices 1 and 3. For the second query, 1 exists between the indices 2 and 5. For the third query, 5 exists between the indices 3 and 5. ``` **樸素方法**： 樸素方法是針對每個查詢遍歷從`L`到`R`的元素，線性搜索`X`。在最壞的情況下，從`L`到`R`可以有`N`個元素，因此 每個查詢的最差情況時間復雜度為`O(n)`。 因此，對于所有`Q`查詢，時間復??雜度將變為`O(Q * N)`。 **使用聯合查找方法**： 此方法僅檢查所有連續相等值中的一個元素。 如果`X`不等于這些值，則算法會跳過所有其他相等的元素，并繼續遍歷下一個不同的元素。 該算法顯然僅在連續存在大量相等元素時才有用。 **算法**： 1. 將所有連續的相等元素合并為一組。 2. 處理查詢時，從`R`開始。讓`index = R`。 3. 將`a[index]`與`X`進行比較。如果它們相等，則打印`"Yes"`，然后遍歷其余范圍。 否則，跳過所有屬于`a[index]`組的連續元素。 索引等于該組的根索引的 1。 4. 繼續上述步驟，直到找到`X`或直到索引小于`L`。 5. 如果索引小于`L`，則打印`"No"`。 以下是上述想法的實現。 ## C++ ```cpp // Program to determine if the element // exists for different range queries #include <bits/stdc++.h> using namespace std; // Structure to represent a query range struct Query { ????int L, R, X; }; const int maxn = 100; int root[maxn]; // Find the root of the group containing // the element at index x int find(int x) { ????return x == root[x] ? x : root[x] = ????????????????find(root[x]); } // merge the two groups containing elements // at indices x and y into one group int uni(int x, int y) { ????int p = find(x), q = find(y); ????if (p != q) { ????????root[p] = root[q]; ????} } void initialize(int a[], int n, Query q[], int m) { ????// make n subsets with every ????// element as its root ????for (int i = 0; i < n; i++) ????????root[i] = i; ????// consecutive elements equal in value are ????// merged into one single group ????for (int i = 1; i < n; i++) ????????if (a[i] == a[i - 1]) ????????????uni(i, i - 1); } // Driver code int main() { ????int a[] = { 1, 1, 5, 4, 5 }; ????int n = sizeof(a) / sizeof(a[0]); ????Query q[] = { { 0, 2, 2 }, { 1, 4, 1 }, ??????????????????{ 2, 4, 5 } }; ????int m = sizeof(q) / sizeof(q[0]); ????initialize(a, n, q, m); ????for (int i = 0; i < m; i++) ????{ ????????int flag = 0; ????????int l = q[i].L, r = q[i].R, x = q[i].X; ????????int p = r; ????????while (p >= l) ????????{ ????????????// check if the current element in ????????????// consideration is equal to x or not ????????????// if it is equal, then x exists in the range ????????????if (a[p] == x) ????????????{ ????????????????flag = 1; ????????????????break; ????????????} ????????????p = find(p) - 1; ????????} ????????// Print if x exists or not ????????if (flag != 0) ????????????cout << x << " exists between [" << l? ?????????????????<< ", " << r << "] " << endl; ????????else ????????????cout << x << " does not exist between ["? ????????????????<< l << ", " << r? << "] " << endl; ????} } ```