Given an array arr[] consisting of N integers and a 2D array Q[][] consisting of queries of the following two types:
- 1 L R: Print the count of numbers from the range [L, R] having only a single set bit.
- 2 X V: Update the array element at Xth index with V.
Examples:
Input: arr[] = { 12, 11, 16, 2, 32 }, Q[][] = { { 1, 0, 2 }, { 2, 4, 24 }, { 1, 1, 4 } }
Output: 1 2
Explanation:
- Query 1: Print the count of array elements with only a single bit in the range of indices [0, 2], i.e. {16}.
- Query 2: Set arr[4] = 24. Therefore, the array arr[] modifies to {12, 11, 16, 24, 5}.
- Query 3: Print the count of array elements with only a single bit in the range of indices [1, 4], i.e. {16, 32}.
Input: arr[] = { 2, 1, 101, 11, 4 }, Q[][] = { { 1, 2, 4 }, { 2, 4, 12 }, { 1, 2, 4 } }
Output: 1 0
Explanation:
- Query 1: Print the count of array elements with only a single bit in the range of indices [2, 4], i.e. {4}.
- Query 2: Set arr[4] = 24, which modifies the array to arr[] = { 2, 1, 101, 11, 12}.
- Query 3: Print the count of array elements with only a single bit in the range of indices [2, 4]. But no array elements from the given range of indices contains only a single bit.
Naive Approach: The simplest approach is to traverse the array over the range of indices [L, R] for each query and for each element, check if it has exactly one set bit or not. Increment count for every array element for which it is found to be true. After traversing the entire range, print the value of count. For queries of type 2, simply arr[X] = V.
Time Complexity: O(N * Q * log(N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using a Segment Tree. Follow the steps below to solve the problem:
- Define a function, check(S) to check if integer contains only one set bit.
- Initialize 3 variables: ss, se, and si to store the starting point of the current segment, ending point of the current segment, and current node value in the segment tree respectively.
- Define a function, say build_seg(ss, se, si), to build a segment tree Similar to the sum segment tree, each node storing the count of elements with only a single bit in its subtree:
- If ss == se, tree[s[i]] = check (arr[ss] )
- Otherwise, traverse the left subtree and right subtree.
- Now, update the current node as tree[si] = tree[2 * si + 1]+ tree[2 * si + 2].
- Define a function, say update( ss, se, si, X, V), to point update a value in the array arr[]:
- If current node is leaf node, i.e ss == se then update the tree[si] = check(V).
- Otherwise, search for the Xth index i.e if X ? (ss + se) / 2 then Traverse to the left subtree i.e update(ss, mid, 2 * si + 1, X, V). Otherwise, traverse to the right subtree i.e update(mid + 1, se, 2 * si + 2, X, V).
- Update the current node.
- Define a function say query(ss, se, si, L, R) to count numbers having only a single bit in the range [L, R]:
- Check if the current segment [L, R] does not intersect with [ss, se] then return 0.
- Otherwise, if ss >= L and se ? R then return tree[si].
- If none of the above conditions satisfies then return query(ss, mid, L, R, 2 * si + 1)+query(mid + 1, se, L, R, 2 * si + 2).
- For query of type { 1, L, R }, print the query(0, N-1, 0, L, R).
- For query of type { 2, X, V }, update the value in the tree, update(0, N-1, 0, X, V).
Below is the implementation of the above approach:
C++
// C++ implementation // for above approach #include <bits/stdc++.h> using namespace std; // Check if N has only // one set bit bool check( int N) { if (N == 0) return 0; return !(N & (N - 1)); } // Function to build segment tree void build_seg_tree( int ss, int se, int si, int tree[], int arr[]) { // If se is leaf node if (ss == se) { // Update the node tree[si] = check(arr[ss]); return ; } // Stores mid value of segment [ss, se] int mid = (ss + se) / 2; // Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1, tree, arr); // Recursive call for right Subtree build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr); // Update the Current Node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Function to update a value at Xth index void update( int ss, int se, int si, int X, int V, int tree[], int arr[]) { if (ss == se) { // If ss is equal to X if (ss == X) { // Update the Xth node arr[X] = V; // Update the tree tree[si] = check(V); } return ; } // Stores the mid of segment [ss, se] int mid = (ss + se) / 2; if (X <= mid) update(ss, mid, 2 * si + 1, X, V, tree, arr); else update(mid + 1, se, 2 * si + 2, X, V, tree, arr); // Update current node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Count of numbers // having one set bit int query( int l, int r, int ss, int se, int si, int tree[]) { // If L > se or R < ss // Invalid Range if (r < ss || l > se) return 0; // If [ss, se] lies // inside the [L, R] if (l <= ss && r >= se) return tree[si]; // Stores the mid of segment [ss, se] int mid = (ss + se) / 2; // Return the sum after recursively // traversing left and right subtree return query(l, r, ss, mid, 2 * si + 1, tree) + query(l, r, mid + 1, se, 2 * si + 2, tree); } // Function to solve queries void Query( int arr[], int N, vector<vector< int > > Q) { // Initialise Segment tree int tree[4 * N] = { 0 }; // Build segment tree build_seg_tree(0, N - 1, 0, tree, arr); // Perform queries for ( int i = 0; i < ( int )Q.size(); i++) { if (Q[i][0] == 1) cout << query(Q[i][1], Q[i][2], 0, N - 1, 0, tree) << " " ; else update(0, N - 1, 0, Q[i][1], Q[i][2], tree, arr); } } // Driver Code int main() { // Input int arr[] = { 12, 11, 16, 2, 32 }; vector<vector< int > > Q{ { 1, 0, 2 }, { 2, 4, 24 }, { 1, 1, 4 } }; int N = sizeof (arr) / sizeof (arr[0]); // Function call to // solve queries Query(arr, N, Q); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Check if N has only // one set bit static int check( int N) { if (Integer.bitCount(N) == 1 ) return 1 ; else return 0 ; } // Function to build segment tree static void build_seg_tree( int ss, int se, int si, int tree[], int arr[]) { // If se is leaf node if (ss == se) { // Update the node tree[si] = check(arr[ss]); return ; } // Stores mid value of segment [ss, se] int mid = (ss + se) / 2 ; // Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1 , tree, arr); // Recursive call for right Subtree build_seg_tree(mid + 1 , se, 2 * si + 2 , tree, arr); // Update the Current Node tree[si] = tree[ 2 * si + 1 ] + tree[ 2 * si + 2 ]; } // Function to update a value at Xth index static void update( int ss, int se, int si, int X, int V, int tree[], int arr[]) { if (ss == se) { // If ss is equal to X if (ss == X) { // Update the Xth node arr[X] = V; // Update the tree tree[si] = check(V); } return ; } // Stores the mid of segment [ss, se] int mid = (ss + se) / 2 ; if (X <= mid) update(ss, mid, 2 * si + 1 , X, V, tree, arr); else update(mid + 1 , se, 2 * si + 2 , X, V, tree, arr); // Update current node tree[si] = tree[ 2 * si + 1 ] + tree[ 2 * si + 2 ]; } // Count of numbers // having one set bit static int query( int l, int r, int ss, int se, int si, int tree[]) { // If L > se or R < ss // Invalid Range if (r < ss || l > se) return 0 ; // If [ss, se] lies // inside the [L, R] if (l <= ss && r >= se) return tree[si]; // Stores the mid of segment [ss, se] int mid = (ss + se) / 2 ; // Return the sum after recursively // traversing left and right subtree return query(l, r, ss, mid, 2 * si + 1 , tree) + query(l, r, mid + 1 , se, 2 * si + 2 , tree); } // Function to solve queries static void Query( int arr[], int N, int [][] Q) { // Initialise Segment tree int tree[] = new int [ 4 * N]; // Build segment tree build_seg_tree( 0 , N - 1 , 0 , tree, arr); // Perform queries for ( int i = 0 ; i < Q.length; i++) { if (Q[i][ 0 ] == 1 ) System.out.print(query(Q[i][ 1 ], Q[i][ 2 ], 0 , N - 1 , 0 , tree) + " " ); else update( 0 , N - 1 , 0 , Q[i][ 1 ], Q[i][ 2 ], tree, arr); } } // Driver Code public static void main(String[] args) { int arr[] = { 12 , 11 , 16 , 2 , 32 }; int [][] Q = { { 1 , 0 , 2 }, { 2 , 4 , 24 }, { 1 , 1 , 4 } }; int N = arr.length; // Function call to // solve queries Query(arr, N, Q); } } // This code is contributed by hemanthsawarna1506. |
Python3
# Python3 implementation of # the above approach # Check if N has only # one set bit def check(N) : if (N = = 0 ): return 0 return ((N & (N - 1 )) = = 0 ) # Function to build segment tree def build_seg_tree(ss, se, si, tree, arr) : # If se is leaf node if (ss = = se) : # Update the node tree[si] = check(arr[ss]) return # Stores mid value of segment [ss, se] mid = (ss + se) / / 2 # Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1 , tree, arr) # Recursive call for right Subtree build_seg_tree(mid + 1 , se, 2 * si + 2 , tree, arr) # Update the Current Node tree[si] = tree[ 2 * si + 1 ] + tree[ 2 * si + 2 ] # Function to update a value at Xth index def update(ss, se, si, X, V, tree, arr) : if (ss = = se) : # If ss is equal to X if (ss = = X) : # Update the Xth node arr[X] = V # Update the tree tree[si] = check(V) return # Stores the mid of segment [ss, se] mid = (ss + se) / / 2 if (X < = mid): update(ss, mid, 2 * si + 1 , X, V, tree, arr) else : update(mid + 1 , se, 2 * si + 2 , X, V, tree, arr) # Update current node tree[si] = tree[ 2 * si + 1 ] + tree[ 2 * si + 2 ] # Count of numbers # having one set bit def query(l, r, ss, se, si, tree) : # If L > se or R < ss # Invalid Range if (r < ss or l > se): return 0 # If [ss, se] lies # inside the [L, R] if (l < = ss and r > = se): return tree[si] # Stores the mid of segment [ss, se] mid = (ss + se) / / 2 # Return the sum after recursively # traversing left and right subtree return (query(l, r, ss, mid, 2 * si + 1 , tree) + query(l, r, mid + 1 , se, 2 * si + 2 , tree)) # Function to solve queries def Query(arr, N, Q) : # Initialise Segment tree tree = [ 0 ] * ( 4 * N) # Build segment tree build_seg_tree( 0 , N - 1 , 0 , tree, arr) # Perform queries for i in range ( len (Q)): if (Q[i][ 0 ] = = 1 ): print (query(Q[i][ 1 ], Q[i][ 2 ], 0 , N - 1 , 0 , tree), end = " " ) else : update( 0 , N - 1 , 0 , Q[i][ 1 ], Q[i][ 2 ], tree, arr) # Driver Code # Input arr = [ 12 , 11 , 16 , 2 , 32 ] Q = [ [ 1 , 0 , 2 ], [ 2 , 4 , 24 ], [ 1 , 1 , 4 ]] N = len (arr) # Function call to # solve queries Query(arr, N, Q) # This code is contributed by code_hunt. |
C#
// C# implementation // for above approach using System; using System.Collections.Generic; class GFG { // Check if N has only // one set bit static int check( int N) { if (N == 0 || (N & (N - 1)) != 0) return 0; return 1; } // Function to build segment tree static void build_seg_tree( int ss, int se, int si, int [] tree, int [] arr) { // If se is leaf node if (ss == se) { // Update the node tree[si] = check(arr[ss]); return ; } // Stores mid value of segment [ss, se] int mid = (ss + se) / 2; // Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1, tree, arr); // Recursive call for right Subtree build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr); // Update the Current Node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Function to update a value at Xth index static void update( int ss, int se, int si, int X, int V, int [] tree, int [] arr) { if (ss == se) { // If ss is equal to X if (ss == X) { // Update the Xth node arr[X] = V; // Update the tree tree[si] = check(V); } return ; } // Stores the mid of segment [ss, se] int mid = (ss + se) / 2; if (X <= mid) update(ss, mid, 2 * si + 1, X, V, tree, arr); else update(mid + 1, se, 2 * si + 2, X, V, tree, arr); // Update current node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Count of numbers // having one set bit static int query( int l, int r, int ss, int se, int si, int [] tree) { // If L > se or R < ss // Invalid Range if (r < ss || l > se) return 0; // If [ss, se] lies // inside the [L, R] if (l <= ss && r >= se) return tree[si]; // Stores the mid of segment [ss, se] int mid = (ss + se) / 2; // Return the sum after recursively // traversing left and right subtree return query(l, r, ss, mid, 2 * si + 1, tree) + query(l, r, mid + 1, se, 2 * si + 2, tree); } // Function to solve queries static void Query( int [] arr, int N, List<List< int > > Q) { // Initialise Segment tree int [] tree = new int [4 * N]; // Build segment tree build_seg_tree(0, N - 1, 0, tree, arr); // Perform queries for ( int i = 0; i < ( int )Q.Count; i++) { if (Q[i][0] == 1) Console.Write(query(Q[i][1], Q[i][2], 0, N - 1, 0, tree) + " " ); else update(0, N - 1, 0, Q[i][1], Q[i][2], tree, arr); } } // Driver code static void Main() { // Input int [] arr = { 12, 11, 16, 2, 32 }; List<List< int > > Q = new List<List< int >>(); Q.Add( new List< int >( new int []{1, 0, 2})); Q.Add( new List< int >( new int []{2, 4, 24})); Q.Add( new List< int >( new int []{1, 1, 4})); int N = arr.Length; // Function call to // solve queries Query(arr, N, Q); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript implementation // for above approach // Check if N has only // one set bit function check( N) { if (N == 0) return 0; return !(N & (N - 1)); } // Function to build segment tree function build_seg_tree( ss, se, si, tree, arr) { // If se is leaf node if (ss == se) { // Update the node tree[si] = check(arr[ss]); return ; } // Stores mid value of segment [ss, se] var mid = parseInt((ss + se) / 2); // Recursive call for left Subtree build_seg_tree(ss, mid, 2 * si + 1, tree, arr); // Recursive call for right Subtree build_seg_tree(mid + 1, se, 2 * si + 2, tree, arr); // Update the Current Node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Function to update a value at Xth index function update(ss, se, si, X, V, tree, arr) { if (ss == se) { // If ss is equal to X if (ss == X) { // Update the Xth node arr[X] = V; // Update the tree tree[si] = check(V); } return ; } // Stores the mid of segment [ss, se] var mid = parseInt((ss + se) / 2); if (X <= mid) update(ss, mid, 2 * si + 1, X, V, tree, arr); else update(mid + 1, se, 2 * si + 2, X, V, tree, arr); // Update current node tree[si] = tree[2 * si + 1] + tree[2 * si + 2]; } // Count of numbers // having one set bit function query( l, r, ss, se, si, tree) { // If L > se or R < ss // Invalid Range if (r < ss || l > se) return 0; // If [ss, se] lies // inside the [L, R] if (l <= ss && r >= se) return tree[si]; // Stores the mid of segment [ss, se] var mid = parseInt((ss + se) / 2); // Return the sum after recursively // traversing left and right subtree return query(l, r, ss, mid, 2 * si + 1, tree) + query(l, r, mid + 1, se, 2 * si + 2, tree); } // Function to solve queries function Query(arr, N, Q) { // Initialise Segment tree var tree = new Array(4 * N); tree.fill( 0 ); // Build segment tree build_seg_tree(0, N - 1, 0, tree, arr); // Perform queries for ( var i = 0; i < Q.length; i++) { if (Q[i][0] == 1) document.write( query(Q[i][1], Q[i][2], 0, N - 1, 0, tree) + " " ); else update(0, N - 1, 0, Q[i][1], Q[i][2], tree, arr); } } var arr = [ 12, 11, 16, 2, 32 ]; var Q = [ [1, 0, 2 ], [ 2, 4, 24], [ 1, 1, 4 ] ]; var N = arr.length; // Function call to // solve queries Query(arr, N, Q); // This code is contributed by SoumikMondal </script> |
1 2
Time Complexity: O(N*log(N)+Q*log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!