# 給定子數組中小于或等于給定數目的元素數 > 原文： [https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/](https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/) 給定數組`a[]`和查詢數量`q`。 每個查詢都可以用`l, r, x`表示。 您的任務是在`l`到`r`表示的子數組中打印小于或等于`x`的元素數。 例子： ``` Input : arr[] = {2, 3, 4, 5} q = 2 0 3 5 0 2 2 Output : 4 1 Number of elements less than or equal to 5 in arr[0..3] is 4 (all elements) Number of elements less than or equal to 2 in arr[0..2] is 1 (only 2) ``` **樸素方法**每個查詢的樸素方法遍歷子數組并計算給定范圍內的元素數。 **有效方法**的想法是使用-[二進制索引樹](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)。 請注意，在以下步驟中，`x`是必須根據其查找元素的數字，并且子數組由`l`，`r`表示。 步驟 1：按升序對數組進行排序。 步驟 2：根據`x`對查詢升序排序，將位數組初始化為 0。 步驟 3：從第一個查詢開始，遍歷數組，直到數組中的值小于等于`x`。 對于每個這樣的元素，將位更新為等于 1 的值 步驟 4：查詢范圍為`l`至`r`的位數組 ``` // C++ program to answer queries to count number // of elements smaller tban or equal to x. #include<bits/stdc++.h> using namespace std; // structure to hold queries struct Query { ????int l, r, x, idx; }; // structure to hold array struct ArrayElement { ????int val, idx; }; // bool function to sort queries according to k bool cmp1(Query q1, Query q2) { ????return q1.x < q2.x; } // bool function to sort array according to its value bool cmp2(ArrayElement x, ArrayElement y) { ????return x.val < y.val; } // updating the bit array void update(int bit[], int idx, int val, int n) { ????for (; idx<=n; idx +=idx&-idx) ????????bit[idx] += val; } // querying the bit array int query(int bit[], int idx, int n) { ????int sum = 0; ????for (; idx > 0; idx -= idx&-idx) ????????sum += bit[idx]; ????return sum; } void answerQueries(int n, Query queries[], int q, ??????????????????????????????ArrayElement arr[]) { ????// initialising bit array ????int bit[n+1]; ????memset(bit, 0, sizeof(bit)); ????// sorting the array ????sort(arr, arr+n, cmp2); ????// sorting queries ????sort(queries, queries+q, cmp1); ????// current index of array ????int curr = 0; ????// array to hold answer of each Query ????int ans[q]; ????// looping through each Query ????for (int i=0; i<q; i++) ????{ ????????// traversing the array values till it ????????// is less than equal to Query number ????????while (arr[curr].val <= queries[i].x && curr<n) ????????{ ????????????// updating the bit array for the array index ????????????update(bit, arr[curr].idx+1, 1, n); ????????????curr++; ????????} ????????// Answer for each Query will be number of ????????// values less than equal to x upto r minus ????????// number of values less than equal to x ????????// upto l-1 ????????ans[queries[i].idx] = query(bit, queries[i].r+1, n) - ??????????????????????????????query(bit, queries[i].l, n); ????} ????// printing answer for each Query ????for (int i=0 ; i<q; i++) ????????cout << ans[i] << endl; } // driver function int main() { ????// size of array ????int n = 4; ????// initialising array value and index ????ArrayElement arr[n]; ????arr[0].val = 2; ????arr[0].idx = 0; ????arr[1].val = 3; ????arr[1].idx = 1; ????arr[2].val = 4; ????arr[2].idx = 2; ????arr[3].val = 5; ????arr[3].idx = 3; ????// number of queries ????int q = 2; ????Query queries[q]; ????queries[0].l = 0; ????queries[0].r = 2; ????queries[0].x = 2; ????queries[0].idx = 0; ????queries[1].l = 0; ????queries[1].r = 3; ????queries[1].x = 5; ????queries[1].idx = 1; ????answerQueries(n, queries, q, arr); ????return 0; } ``` 輸出： ``` 1 4 ``` 如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。