Queries for number of distinct elements in a subarray
Given a array ‘a[]’ of size n and number of queries q. Each query can be represented by two integers l and r. Your task is to print the number of distinct integers in the subarray l to r. Given a[i] <= 106 Examples:
Input : a[] = {1, 1, 2, 1, 3} q = 3 0 4 1 3 2 4 Output :3 2 3 In query 1, number of distinct integers in a[0...4] is 3 (1, 2, 3) In query 2, number of distinct integers in a[1..3] is 2 (1, 2) In query 3, number of distinct integers in a[2..4] is 3 (1, 2, 3)
The idea is to use Binary Indexed Tree
- Step 1 : Take an array last_visit of size 10^6 where last_visit[i] holds the rightmost index of the number i in the array a. Initialize this array as -1.
- Step 2 : Sort all the queries in ascending order of their right end r.
- Step 3 : Create a Binary Indexed Tree in an array bit[]. Start traversing the array ‘a’ and queries simultaneously and check if last_visit[a[i]] is -1 or not. If it is not, update the bit array with value -1 at the idx last_visit[a[i]].
- Step 4 : Set last_visit[a[i]] = i and update the bit array bit array with value 1 at idx i.
- Step 5 : Answer all the queries whose value of r is equal to i by querying the bit array. This can be easily done as queries are sorted.
C++
// C++ code to find number of distinct numbers // in a subarray #include<bits/stdc++.h> using namespace std; const int MAX = 1000001; // structure to store queries struct Query { int l, r, idx; }; // cmp function to sort queries according to r bool cmp(Query x, Query y) { return x.r < y.r; } // updating the bit array void update( int idx, int val, int bit[], int n) { for (; idx <= n; idx += idx&-idx) bit[idx] += val; } // querying the bit array int query( int idx, int bit[], int n) { int sum = 0; for (; idx>0; idx-=idx&-idx) sum += bit[idx]; return sum; } void answeringQueries( int arr[], int n, Query queries[], int q) { // initialising bit array int bit[n+1]; memset (bit, 0, sizeof (bit)); // holds the rightmost index of any number // as numbers of a[i] are less than or equal to 10^6 int last_visit[MAX]; memset (last_visit, -1, sizeof (last_visit)); // answer for each query int ans[q]; int query_counter = 0; for ( int i=0; i<n; i++) { // If last visit is not -1 update -1 at the // idx equal to last_visit[arr[i]] if (last_visit[arr[i]] !=-1) update (last_visit[arr[i]] + 1, -1, bit, n); // Setting last_visit[arr[i]] as i and updating // the bit array accordingly last_visit[arr[i]] = i; update(i + 1, 1, bit, n); // If i is equal to r of any query store answer // for that query in ans[] while (query_counter < q && queries[query_counter].r == i) { ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n)- query(queries[query_counter].l, bit, n); query_counter++; } } // print answer for each query for ( int i=0; i<q; i++) cout << ans[i] << endl; } // driver code int main() { int a[] = {1, 1, 2, 1, 3}; int n = sizeof (a)/ sizeof (a[0]); Query queries[3]; queries[0].l = 0; queries[0].r = 4; queries[0].idx = 0; queries[1].l = 1; queries[1].r = 3; queries[1].idx = 1; queries[2].l = 2; queries[2].r = 4; queries[2].idx = 2; int q = sizeof (queries)/ sizeof (queries[0]); sort(queries, queries+q, cmp); answeringQueries(a, n, queries, q); return 0; } |
Java
// Java code to find number of distinct numbers // in a subarray import java.io.*; import java.util.*; class GFG { static int MAX = 1000001 ; // structure to store queries static class Query { int l, r, idx; } // updating the bit array static void update( int idx, int val, int bit[], int n) { for (; idx <= n; idx += idx & -idx) bit[idx] += val; } // querying the bit array static int query( int idx, int bit[], int n) { int sum = 0 ; for (; idx > 0 ; idx -= idx & -idx) sum += bit[idx]; return sum; } static void answeringQueries( int [] arr, int n, Query[] queries, int q) { // initialising bit array int [] bit = new int [n + 1 ]; Arrays.fill(bit, 0 ); // holds the rightmost index of any number // as numbers of a[i] are less than or equal to 10^6 int [] last_visit = new int [MAX]; Arrays.fill(last_visit, - 1 ); // answer for each query int [] ans = new int [q]; int query_counter = 0 ; for ( int i = 0 ; i < n; i++) { // If last visit is not -1 update -1 at the // idx equal to last_visit[arr[i]] if (last_visit[arr[i]] != - 1 ) update(last_visit[arr[i]] + 1 , - 1 , bit, n); // Setting last_visit[arr[i]] as i and updating // the bit array accordingly last_visit[arr[i]] = i; update(i + 1 , 1 , bit, n); // If i is equal to r of any query store answer // for that query in ans[] while (query_counter < q && queries[query_counter].r == i) { ans[queries[query_counter].idx] = query(queries[query_counter].r + 1 , bit, n) - query(queries[query_counter].l, bit, n); query_counter++; } } // print answer for each query for ( int i = 0 ; i < q; i++) System.out.println(ans[i]); } // Driver Code public static void main(String[] args) { int a[] = { 1 , 1 , 2 , 1 , 3 }; int n = a.length; Query[] queries = new Query[ 3 ]; for ( int i = 0 ; i < 3 ; i++) queries[i] = new Query(); queries[ 0 ].l = 0 ; queries[ 0 ].r = 4 ; queries[ 0 ].idx = 0 ; queries[ 1 ].l = 1 ; queries[ 1 ].r = 3 ; queries[ 1 ].idx = 1 ; queries[ 2 ].l = 2 ; queries[ 2 ].r = 4 ; queries[ 2 ].idx = 2 ; int q = queries.length; Arrays.sort(queries, new Comparator<Query>() { public int compare(Query x, Query y) { if (x.r < y.r) return - 1 ; else if (x.r == y.r) return 0 ; else return 1 ; } }); answeringQueries(a, n, queries, q); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 code to find number of # distinct numbers in a subarray MAX = 1000001 # structure to store queries class Query: def __init__( self , l, r, idx): self .l = l self .r = r self .idx = idx # updating the bit array def update(idx, val, bit, n): while idx < = n: bit[idx] + = val idx + = idx & - idx # querying the bit array def query(idx, bit, n): summ = 0 while idx: summ + = bit[idx] idx - = idx & - idx return summ def answeringQueries(arr, n, queries, q): # initialising bit array bit = [ 0 ] * (n + 1 ) # holds the rightmost index of # any number as numbers of a[i] # are less than or equal to 10^6 last_visit = [ - 1 ] * MAX # answer for each query ans = [ 0 ] * q query_counter = 0 for i in range (n): # If last visit is not -1 update -1 at the # idx equal to last_visit[arr[i]] if last_visit[arr[i]] ! = - 1 : update(last_visit[arr[i]] + 1 , - 1 , bit, n) # Setting last_visit[arr[i]] as i and # updating the bit array accordingly last_visit[arr[i]] = i update(i + 1 , 1 , bit, n) # If i is equal to r of any query store answer # for that query in ans[] while query_counter < q and queries[query_counter].r = = i: ans[queries[query_counter].idx] = \ query(queries[query_counter].r + 1 , bit, n) - \ query(queries[query_counter].l, bit, n) query_counter + = 1 # print answer for each query for i in range (q): print (ans[i]) # Driver Code if __name__ = = "__main__" : a = [ 1 , 1 , 2 , 1 , 3 ] n = len (a) queries = [Query( 0 , 4 , 0 ), Query( 1 , 3 , 1 ), Query( 2 , 4 , 2 )] q = len (queries) queries.sort(key = lambda x: x.r) answeringQueries(a, n, queries, q) # This code is contributed by # sanjeev2552 |
C#
using System; using System.Linq; class GFG { static int MAX = 1000001; // structure to store queries public class Query { public int l, r, idx; } // updating the bit array public static void update( int idx, int val, int [] bit, int n) { for (; idx <= n; idx += idx & -idx) bit[idx] += val; } // querying the bit array public static int query( int idx, int [] bit, int n) { int sum = 0; for (; idx > 0; idx -= idx & -idx) sum += bit[idx]; return sum; } public static void answeringQueries( int [] arr, int n, Query[] queries, int q) { // initialising bit array int [] bit = new int [n + 1]; Array.Fill(bit, 0); // holds the rightmost index of any number // as numbers of a[i] are less than or equal to 10^6 int [] last_visit = new int [MAX]; Array.Fill(last_visit, -1); // answer for each query int [] ans = new int [q]; int query_counter = 0; for ( int i = 0; i < n; i++) { // If last visit is not -1 update -1 at the // idx equal to last_visit[arr[i]] if (last_visit[arr[i]] != -1) update(last_visit[arr[i]] + 1, -1, bit, n); // Setting last_visit[arr[i]] as i and updating // the bit array accordingly last_visit[arr[i]] = i; update(i + 1, 1, bit, n); // If i is equal to r of any query store answer // for that query in ans[] while (query_counter < q && queries[query_counter].r == i) { ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) - query(queries[query_counter].l, bit, n); query_counter++; } } // print answer for each query for ( int i = 0; i < q; i++) Console.WriteLine(ans[i]); } // Driver Code public static void Main( string [] args) { int [] a = { 1, 1, 2, 1, 3 }; int n = a.Length; Query[] queries = new Query[3]; for ( int i = 0; i < 3; i++) queries[i] = new Query(); queries[0].l = 0; queries[0].r = 4; queries[0].idx = 0; queries[1].l = 1; queries[1].r = 3; queries[1].idx = 1; queries[2].l = 2; queries[2].r = 4; queries[2].idx = 2; int q = queries.Length; Array.Sort(queries, (x, y) => x.r - y.r); answeringQueries(a, n, queries, q); } } |
Javascript
<script> // JavaScript code to find number of // distinct numbers in a subarray const MAX = 1000001 // structure to store queries class Query{ constructor(l, r, idx){ this .l = l this .r = r this .idx = idx } } // updating the bit array function update(idx, val, bit, n){ while (idx <= n){ bit[idx] += val idx += idx & -idx } } // querying the bit array function query(idx, bit, n){ let summ = 0 while (idx){ summ += bit[idx] idx -= idx & -idx } return summ } function answeringQueries(arr, n, queries, q){ // initialising bit array let bit = new Array(n+1).fill(0) // holds the rightmost index of // any number as numbers of a[i] // are less than or equal to 10^6 let last_visit = new Array(MAX).fill(-1) // answer for each query let ans = new Array(q).fill(0); let query_counter = 0 for (let i=0;i<n;i++){ // If last visit is not -1 update -1 at the // idx equal to last_visit[arr[i]] if (last_visit[arr[i]] != -1) update(last_visit[arr[i]] + 1, -1, bit, n) // Setting last_visit[arr[i]] as i and // updating the bit array accordingly last_visit[arr[i]] = i update(i + 1, 1, bit, n) // If i is equal to r of any query store answer // for that query in ans[] while (query_counter < q && queries[query_counter].r == i){ ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) - query(queries[query_counter].l, bit, n) query_counter += 1 } } // print answer for each query for (let i=0;i<q;i++) document.write(ans[i], "</br>" ) } // Driver Code let a = [1, 1, 2, 1, 3] let n = a.length let queries = [ new Query(0, 4, 0), new Query(1, 3, 1), new Query(2, 4, 2)] let q = queries.length queries.sort((x,y) => x.r-y.r) answeringQueries(a, n, queries, q) // This code is contributed by shinjanpatra </script> |
Output:
3 2 3
Time Complexity: O((n+q)*log(n))
Auxiliary Space: O(n+q+MAX)
Contact Us