Related Articles
Queries for elements greater than K in the given index range using Segment Tree
• Difficulty Level : Hard
• Last Updated : 04 Feb, 2021

Given an array arr[] of N elements and a number of queries where each query will contain three integers L, R, and K. For each query, the task is to find the number of elements in the subarray arr[L…R] which are greater than K.
Examples:

Input: arr[] = {7, 3, 9, 13, 5, 4}, q[] = {{0, 3, 6}, {1, 5, 8}}
Output:

Query 1: Only 7, 9 and 13 are greater
than 6 in the subarray {7, 3, 9, 13}.
Query 2: Only 9 and 13 are greater
than 8 in the subarray {3, 9, 13, 5, 4}.

Input: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, q[] = {{0, 7, 3}, {4, 6, 10}}
Output:

Prerequisite: Segment tree
Naive approach: Find the answer for each query by simply traversing the array from index l till r and keep adding 1 to the count whenever the array element is greater than k. The Time Complexity of this approach will be O(n * q).
Efficient approach: Build a Segment Tree with a vector at each node containing all the elements of the sub-range in sorted order. Answer each query using the segment tree where Binary Search can be used to calculate how many numbers are present in each node whose sub-range lies within the query range which is greater than K. Time complexity of this approach will be O(q * log(n) * log(n))
Below is the implementation of the above approach:

## C++

 `// C++ implementation of the approach``#include ``using` `namespace` `std;` `// Merge procedure to merge two``// vectors into a single vector``vector<``int``> merge(vector<``int``>& v1, vector<``int``>& v2)``{``    ``int` `i = 0, j = 0;` `    ``// Final vector to return``    ``// after merging``    ``vector<``int``> v;` `    ``// Loop continues until it reaches``    ``// the end of one of the vectors``    ``while` `(i < v1.size() && j < v2.size()) {``        ``if` `(v1[i] <= v2[j]) {``            ``v.push_back(v1[i]);``            ``i++;``        ``}``        ``else` `{``            ``v.push_back(v2[j]);``            ``j++;``        ``}``    ``}` `    ``// Here, simply add the remaining``    ``// elements to the vector v``    ``for` `(``int` `k = i; k < v1.size(); k++)``        ``v.push_back(v1[k]);``    ``for` `(``int` `k = j; k < v2.size(); k++)``        ``v.push_back(v2[k]);``    ``return` `v;``}` `// Procedure to build the segment tree``void` `buildTree(vector<``int``>* tree, ``int``* arr,``               ``int` `index, ``int` `s, ``int` `e)``{` `    ``// Reached the leaf node``    ``// of the segment tree``    ``if` `(s == e) {``        ``tree[index].push_back(arr[s]);``        ``return``;``    ``}` `    ``// Recursively call the buildTree``    ``// on both the nodes of the tree``    ``int` `mid = (s + e) / 2;``    ``buildTree(tree, arr, 2 * index, s, mid);``    ``buildTree(tree, arr, 2 * index + 1, mid + 1, e);` `    ``// Storing the final vector after merging``    ``// the two of its sorted child vector``    ``tree[index] = merge(tree[2 * index], tree[2 * index + 1]);``}` `// Query procedure to get the answer``// for each query l and r are query range``int` `query(vector<``int``>* tree, ``int` `index, ``int` `s,``          ``int` `e, ``int` `l, ``int` `r, ``int` `k)``{` `    ``// out of bound or no overlap``    ``if` `(r < s || l > e)``        ``return` `0;` `    ``// Complete overlap``    ``// Query range completely lies in``    ``// the segment tree node range``    ``if` `(s >= l && e <= r) {``        ``// binary search to find index of k``        ``return` `(tree[index].size()``                ``- (lower_bound(tree[index].begin(),``                               ``tree[index].end(), k)``                   ``- tree[index].begin()));``    ``}` `    ``// Partially overlap``    ``// Query range partially lies in``    ``// the segment tree node range``    ``int` `mid = (s + e) / 2;``    ``return` `(query(tree, 2 * index, s,``                  ``mid, l, r, k)``            ``+ query(tree, 2 * index + 1, mid + 1,``                    ``e, l, r, k));``}` `// Function to perform the queries``void` `performQueries(``int` `L[], ``int` `R[], ``int` `K[],``                    ``int` `n, ``int` `q, vector<``int``> tree[])``{``    ``for` `(``int` `i = 0; i < q; i++) {``        ``cout << query(tree, 1, 0, n - 1,``                      ``L[i] - 1, R[i] - 1, K[i])``             ``<< endl;``    ``}``}` `// Driver code``int` `main()``{``    ``int` `arr[] = { 7, 3, 9, 13, 5, 4 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr);``    ``vector<``int``> tree[4 * n + 1];``    ``buildTree(tree, arr, 1, 0, n - 1);` `    ``// 1-based indexing``    ``int` `L[] = { 1, 2 };``    ``int` `R[] = { 4, 6 };``    ``int` `K[] = { 6, 8 };` `    ``// Number of queries``    ``int` `q = ``sizeof``(L) / ``sizeof``(L);` `    ``performQueries(L, R, K, n, q, tree);` `    ``return` `0;``}`

## Java

 `// Java implementation of the approach``import` `java.util.*;` `class` `GFG {` `    ``// Merge procedure to merge two``    ``// vectors into a single vector``    ``static` `Vector merge(Vector v1,``                               ``Vector v2)``    ``{``        ``int` `i = ``0``, j = ``0``;` `        ``// Final vector to return``        ``// after merging``        ``Vector v = ``new` `Vector<>();` `        ``// Loop continues until it reaches``        ``// the end of one of the vectors``        ``while` `(i < v1.size() && j < v2.size())``        ``{``            ``if` `(v1.elementAt(i) <= v2.elementAt(j))``            ``{``                ``v.add(v1.elementAt(i));``                ``i++;``            ``}``            ``else``            ``{``                ``v.add(v2.elementAt(j));``                ``j++;``            ``}``        ``}` `        ``// Here, simply add the remaining``        ``// elements to the vector v``        ``for` `(``int` `k = i; k < v1.size(); k++)``            ``v.add(v1.elementAt(k));``        ``for` `(``int` `k = j; k < v2.size(); k++)``            ``v.add(v2.elementAt(k));``        ``return` `v;``    ``}` `    ``// Procedure to build the segment tree``    ``static` `void` `buildTree(Vector[] tree, ``int``[] arr,``                        ``int` `index, ``int` `s, ``int` `e)``    ``{` `        ``// Reached the leaf node``        ``// of the segment tree``        ``if` `(s == e)``        ``{``            ``tree[index].add(arr[s]);``            ``return``;``        ``}` `        ``// Recursively call the buildTree``        ``// on both the nodes of the tree``        ``int` `mid = (s + e) / ``2``;``        ``buildTree(tree, arr, ``2` `* index, s, mid);``        ``buildTree(tree, arr, ``2` `* index + ``1``, mid + ``1``, e);` `        ``// Storing the final vector after merging``        ``// the two of its sorted child vector``        ``tree[index] = merge(tree[``2` `* index], tree[``2` `* index + ``1``]);``    ``}` `    ``// Query procedure to get the answer``    ``// for each query l and r are query range``    ``static` `int` `query(Vector[] tree, ``int` `index, ``int` `s,``                    ``int` `e, ``int` `l, ``int` `r, ``int` `k)``    ``{` `        ``// out of bound or no overlap``        ``if` `(r < s || l > e)``            ``return` `0``;` `        ``// Complete overlap``        ``// Query range completely lies in``        ``// the segment tree node range``        ``if` `(s >= l && e <= r)``        ``{``            ` `            ``// binary search to find index of k``            ``return` `(tree[index].size() - lowerBound(tree[index],``                    ``tree[index].size(), k));``        ``}` `        ``// Partially overlap``        ``// Query range partially lies in``        ``// the segment tree node range``        ``int` `mid = (s + e) / ``2``;``        ``return` `(query(tree, ``2` `* index, s, mid, l, r, k) +``                ``query(tree, ``2` `* index + ``1``, mid + ``1``, e, l, r, k));``    ``}` `    ``// Function to perform the queries``    ``static` `void` `performQueries(``int` `L[], ``int` `R[], ``int` `K[],``                        ``int` `n, ``int` `q, Vector tree[])``    ``{``        ``for` `(``int` `i = ``0``; i < q; i++)``        ``{``            ``System.out.println(query(tree, ``1``, ``0``, n - ``1``,``                                    ``L[i] - ``1``, R[i] - ``1``, K[i]));``        ``}``    ``}` `    ``static` `int` `lowerBound(Vector array,``                        ``int` `length, ``int` `value)``    ``{``        ``int` `low = ``0``;``        ``int` `high = length;``        ``while` `(low < high)``        ``{``            ``final` `int` `mid = (low + high) / ``2``;``            ``if` `(value <= array.elementAt(mid))``            ``{``                ``high = mid;``            ``}``            ``else``            ``{``                ``low = mid + ``1``;``            ``}``        ``}``        ``return` `low;``    ``}` `    ``// Driver Code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `arr[] = { ``7``, ``3``, ``9``, ``13``, ``5``, ``4` `};``        ``int` `n = arr.length;``        ``@SuppressWarnings``(``"unchecked"``)``        ``Vector[] tree = ``new` `Vector[``4` `* n + ``1``];``        ``for` `(``int` `i = ``0``; i < (``4` `* n + ``1``); i++)``        ``{``            ``tree[i] = ``new` `Vector<>();``        ``}` `        ``buildTree(tree, arr, ``1``, ``0``, n - ``1``);` `        ``// 1-based indexing``        ``int` `L[] = { ``1``, ``2` `};``        ``int` `R[] = { ``4``, ``6` `};``        ``int` `K[] = { ``6``, ``8` `};` `        ``// Number of queries``        ``int` `q = L.length;` `        ``performQueries(L, R, K, n, q, tree);``    ``}``}` `// This code is contributed by``// sanjeev2552`

## Python3

 `# Python3 implementation of the approach``from` `bisect ``import` `bisect_left as lower_bound` `# Merge procedure to merge two``# vectors into a single vector``def` `merge(v1, v2):``    ``i ``=` `0``    ``j ``=` `0` `    ``# Final vector to return``    ``# after merging``    ``v ``=` `[]` `    ``# Loop continues until it reaches``    ``# the end of one of the vectors``    ``while` `(i < ``len``(v1) ``and` `j < ``len``(v2)):``        ``if` `(v1[i] <``=` `v2[j]):``            ``v.append(v1[i])``            ``i ``+``=` `1``        ``else``:``            ``v.append(v2[j])``            ``j ``+``=` `1` `    ``# Here, simply add the remaining``    ``# elements to the vector v``    ``for` `k ``in` `range``(i, ``len``(v1)):``        ``v.append(v1[k])``    ``for` `k ``in` `range``(j, ``len``(v2)):``        ``v.append(v2[k])``    ``return` `v` `# Procedure to build the segment tree``def` `buildTree(tree,arr,index, s, e):` `    ``# Reached the leaf node``    ``# of the segment tree``    ``if` `(s ``=``=` `e):``        ``tree[index].append(arr[s])``        ``return` `    ``# Recursively call the buildTree``    ``# on both the nodes of the tree``    ``mid ``=` `(s ``+` `e) ``/``/` `2``    ``buildTree(tree, arr, ``2` `*` `index, s, mid)``    ``buildTree(tree, arr, ``2` `*` `index ``+` `1``, mid ``+` `1``, e)` `    ``# Storing the final vector after merging``    ``# the two of its sorted child vector``    ``tree[index] ``=` `merge(tree[``2` `*` `index], tree[``2` `*` `index ``+` `1``])` `# Query procedure to get the answer``# for each query l and r are query range``def` `query(tree, index, s, e, l, r, k):` `    ``# out of bound or no overlap``    ``if` `(r < s ``or` `l > e):``        ``return` `0` `    ``# Complete overlap``    ``# Query range completely lies in``    ``# the segment tree node range``    ``if` `(s >``=` `l ``and` `e <``=` `r):``        ` `        ``# binary search to find index of k``        ``return` `len``(tree[index]) ``-` `(lower_bound(tree[index], k))` `    ``# Partially overlap``    ``# Query range partially lies in``    ``# the segment tree node range``    ``mid ``=` `(s ``+` `e) ``/``/` `2``    ``return` `(query(tree, ``2` `*` `index, s,mid, l, r, k)``            ``+` `query(tree, ``2` `*` `index ``+` `1``, mid ``+` `1``,e, l, r, k))` `# Function to perform the queries``def` `performQueries(L, R, K,n, q,tree):``    ``for` `i ``in` `range``(q):``        ``print``(query(tree, ``1``, ``0``, n ``-` `1``,L[i] ``-` `1``, R[i] ``-` `1``, K[i]))` `# Driver code``if` `__name__ ``=``=` `'__main__'``:``    ``arr ``=` `[``7``, ``3``, ``9``, ``13``, ``5``, ``4``]``    ``n ``=` `len``(arr)``    ``tree ``=` `[[] ``for` `i ``in` `range``(``4` `*` `n ``+` `1``)]``    ``buildTree(tree, arr, ``1``, ``0``, n ``-` `1``)` `    ``# 1-based indexing``    ``L ``=` `[``1``, ``2``]``    ``R ``=` `[``4``, ``6``]``    ``K ``=` `[``6``, ``8``]` `    ``# Number of queries``    ``q ``=` `len``(L)` `     ``performQueries(L, R, K, n, q, tree)``     ` `# This code is contributed by mohit kumar 29        `

## C#

 `// C# implementation of the approach``using` `System;``using` `System.Collections.Generic;` `class` `GFG {`` ` `    ``// Merge procedure to merge two``    ``// vectors into a single vector``    ``static` `List<``int``> merge(List<``int``> v1,``                               ``List<``int``> v2)``    ``{``        ``int` `i = 0, j = 0;`` ` `        ``// Final vector to return``        ``// after merging``        ``List<``int``> v = ``new` `List<``int``>();`` ` `        ``// Loop continues until it reaches``        ``// the end of one of the vectors``        ``while` `(i < v1.Count && j < v2.Count)``        ``{``            ``if` `(v1[i] <= v2[j])``            ``{``                ``v.Add(v1[i]);``                ``i++;``            ``}``            ``else``            ``{``                ``v.Add(v2[j]);``                ``j++;``            ``}``        ``}`` ` `        ``// Here, simply add the remaining``        ``// elements to the vector v``        ``for` `(``int` `k = i; k < v1.Count; k++)``            ``v.Add(v1[k]);``        ``for` `(``int` `k = j; k < v2.Count; k++)``            ``v.Add(v2[k]);``        ``return` `v;``    ``}`` ` `    ``// Procedure to build the segment tree``    ``static` `void` `buildTree(List<``int``>[] tree, ``int``[] arr,``                        ``int` `index, ``int` `s, ``int` `e)``    ``{`` ` `        ``// Reached the leaf node``        ``// of the segment tree``        ``if` `(s == e)``        ``{``            ``tree[index].Add(arr[s]);``            ``return``;``        ``}`` ` `        ``// Recursively call the buildTree``        ``// on both the nodes of the tree``        ``int` `mid = (s + e) / 2;``        ``buildTree(tree, arr, 2 * index, s, mid);``        ``buildTree(tree, arr, 2 * index + 1, mid + 1, e);`` ` `        ``// Storing the readonly vector after merging``        ``// the two of its sorted child vector``        ``tree[index] = merge(tree[2 * index], tree[2 * index + 1]);``    ``}`` ` `    ``// Query procedure to get the answer``    ``// for each query l and r are query range``    ``static` `int` `query(List<``int``>[] tree, ``int` `index, ``int` `s,``                    ``int` `e, ``int` `l, ``int` `r, ``int` `k)``    ``{`` ` `        ``// out of bound or no overlap``        ``if` `(r < s || l > e)``            ``return` `0;`` ` `        ``// Complete overlap``        ``// Query range completely lies in``        ``// the segment tree node range``        ``if` `(s >= l && e <= r)``        ``{``             ` `            ``// binary search to find index of k``            ``return` `(tree[index].Count - lowerBound(tree[index],``                    ``tree[index].Count, k));``        ``}`` ` `        ``// Partially overlap``        ``// Query range partially lies in``        ``// the segment tree node range``        ``int` `mid = (s + e) / 2;``        ``return` `(query(tree, 2 * index, s, mid, l, r, k) +``                ``query(tree, 2 * index + 1, mid + 1, e, l, r, k));``    ``}`` ` `    ``// Function to perform the queries``    ``static` `void` `performQueries(``int` `[]L, ``int` `[]R, ``int` `[]K,``                        ``int` `n, ``int` `q, List<``int``> []tree)``    ``{``        ``for` `(``int` `i = 0; i < q; i++)``        ``{``            ``Console.WriteLine(query(tree, 1, 0, n - 1,``                                    ``L[i] - 1, R[i] - 1, K[i]));``        ``}``    ``}`` ` `    ``static` `int` `lowerBound(List<``int``> array,``                        ``int` `length, ``int` `value)``    ``{``        ``int` `low = 0;``        ``int` `high = length;``        ``while` `(low < high)``        ``{``            ``int` `mid = (low + high) / 2;``            ``if` `(value <= array[mid])``            ``{``                ``high = mid;``            ``}``            ``else``            ``{``                ``low = mid + 1;``            ``}``        ``}``        ``return` `low;``    ``}`` ` `    ``// Driver Code``    ``public` `static` `void` `Main(String[] args)``    ``{``        ``int` `[]arr = { 7, 3, 9, 13, 5, 4 };``        ``int` `n = arr.Length;``        ``List<``int``>[] tree = ``new` `List<``int``>[4 * n + 1];``        ``for` `(``int` `i = 0; i < (4 * n + 1); i++)``        ``{``            ``tree[i] = ``new` `List<``int``>();``        ``}`` ` `        ``buildTree(tree, arr, 1, 0, n - 1);`` ` `        ``// 1-based indexing``        ``int` `[]L = { 1, 2 };``        ``int` `[]R = { 4, 6 };``        ``int` `[]K = { 6, 8 };`` ` `        ``// Number of queries``        ``int` `q = L.Length;`` ` `        ``performQueries(L, R, K, n, q, tree);``    ``}``}` `// This code is contributed by PrinciRaj1992`
Output:

```3
2```

Another Approach:

Another way of doing it using segment trees is by storing the first element greater than in each node (if present) in that range, otherwise storing 0.

Here, we need to consider 3 cases for building the tree.

1. If both left and right children contain a number other than 0, the answer is always the left child. (we need to consider the very first occurrence of the number greater than K.)
2. If any one of the left or right child contains 0, the answer is always a number other than 0.
3. If both left and right children contain 0, the answer is always 0 (indicating that no number greater than K is present in that range).

The query function remains the same as always.

Consider the following example:  arr[] = {7, 3, 9, 13, 5, 4} , K = 6

The tree in this case will look like this: Below is the implementation of the above approach:

## C++

 `// C++ implementation of the approach``#include ``using` `namespace` `std;` `vector<``int``> arr(1000000), tree(4 * arr.size());` `// combine function to make parent node``int` `combine(``int` `a, ``int` `b)``{``    ``if` `(a != 0 && b != 0) {``        ``return` `a;``    ``}``    ``if` `(a >= b) {``        ``return` `a;``    ``}``    ``return` `b;``}` `// building the tree``void` `buildTree(``int` `ind, ``int` `low, ``int` `high, ``int` `x)``{``    ``// leaf node``    ``if` `(low == high) {``        ``if` `(arr[low] > x) {``            ``tree[ind] = arr[low];``        ``}``        ``else` `{``            ``tree[ind] = 0;``        ``}``        ``return``;``    ``}``    ``int` `mid = (low + high) / 2;``    ``buildTree(2 * ind + 1, low, mid, x);``    ``buildTree(2 * ind + 2, mid + 1, high, x);` `    ``// merging the nodes while backtracking.``    ``tree[ind]``        ``= combine(tree[2 * ind + 1], tree[2 * ind + 2]);``}``// performing query``int` `query(``int` `ind, ``int` `low, ``int` `high, ``int` `l, ``int` `r)``{``    ``int` `mid = (low + high) / 2;``    ``// Out of Bounds``    ``if` `(low > r || high < l) {``        ``return` `0;``    ``}``    ``// completely overlaps``    ``if` `(l <= low && r >= high) {``        ``return` `tree[ind];``    ``}``    ``// partially overlaps``    ``return` `combine(query(2 * ind + 1, low, mid, l, r),``                   ``query(2 * ind + 2, mid + 1, high, l, r));``}` `// Driver Code``int` `main()``{``    ``arr = { 7, 3, 9, 13, 5, 4 };``    ``int` `n = 6;``    ``int` `k = 6;` `    ``// 1-based indexing``    ``int` `l = 1, r = 4;``    ``buildTree(0, 0, n - 1, k);``    ``cout << query(0, 0, n - 1, l - 1, r - 1);``    ``return` `0;``}``// This code is contributed by yashbeersingh42`

Output:

`7`

Time Complexity: O(N * log N) to build the tree and O(log N) for each query.

Space Complexity: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer Geeks Classes Live and Geeks Classes Live USA

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.6213561,"math_prob":0.98257554,"size":14274,"snap":"2021-21-2021-25","text_gpt3_token_len":4857,"char_repetition_ratio":0.1394534,"word_repetition_ratio":0.4377093,"special_character_ratio":0.38790807,"punctuation_ratio":0.19319256,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997464,"pos_list":[0,1,2],"im_url_duplicate_count":[null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-05-06T01:08:25Z\",\"WARC-Record-ID\":\"<urn:uuid:5360dcdf-839c-4c76-adcd-d197efb3f410>\",\"Content-Length\":\"208365\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:1e091b6e-192d-4812-a380-3616bac89905>\",\"WARC-Concurrent-To\":\"<urn:uuid:ae797f9b-c135-40a8-bb07-1e144faded73>\",\"WARC-IP-Address\":\"23.62.230.9\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/queries-for-elements-greater-than-k-in-the-given-index-range-using-segment-tree/?ref=rp\",\"WARC-Payload-Digest\":\"sha1:KWQHBPMUZBGK6XGB4H26OJ27OOYZXOFO\",\"WARC-Block-Digest\":\"sha1:HOUOFEWHTOLPU3EGRYKS6EAOJE7N4IC4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-21/CC-MAIN-2021-21_segments_1620243988724.75_warc_CC-MAIN-20210505234449-20210506024449-00349.warc.gz\"}"}