Given an array arr[] of N integers, an integer K, and Q queries of the type as explained below:
- (1, L, R): If the query is of type 1, then find the number of Ks over the range [L, R].
- (2, P, X): If the query is of type 2, then update the array element at index P to X.
The task is to perform the queries on the given Array and print the result accordingly.
Examples:
Input: K = 0, arr[] = {9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0}, query[][2] = {{1, 5, 14 }, {2, 6, 1 }, {1, 0, 8 }, {2, 13, 0 }, {1, 6, 18 } }
Output: 5
3
6
Explanation:
Following are the values of queries performed:
- first query is of type 1, then the count of 0s(= K) in the range [5, 14] is 5.
- second query is of type 2 so update the value of array element at index P = 6 to X = 1 i.e., arr[6] = 1.
The modified array is {9 5 7 6 9 0 1 0 0 5 6 7 3 9 0 7 0 9 0}.- third query is of type 1, then the count of 0s(= K) in the range [0, 8] is 3.
- fourth query is of type 2 so update the value of array element at index P = 13 to X = 0 i.e., arr[13] = 0.
The modified array is {9 5 7 6 9 0 1 0 0 5 6 7 3 0 0 7 0 9 0}.- fifth query is of type 1, then the count of 0s in the range [6, 18] is 6.
Therefore, print 5, 3, and 6 as the answer to the queries.
Input: K = 6, arr[] = {9, 5, 7, 6}, query[][2] = {{1, 1, 2}, {2, 0, 0} }
Output: 0
Naive Approach: The simplest approach to solve the given problem is to change the array element for the query of the second type and for the first type of query, traverse the array over the range [L, R] and print the count of K in it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform all the queriesvoid performQueries(int n, int q, int k, vector<int>& arr, vector<vector<int> >& query){ for (int i = 1; i <= q; i++) { // Stores the count of 0s int count = 0; // Count the number of 0s for // query of type 1 if (query[i - 1][0] == 1) { for (int j = query[i - 1][1]; j <= query[i - 1][2]; j++) { if (arr[j] == k) count++; } cout << count << endl; } // Update the array element for // query of type 2 else { arr[query[i - 1][1]] = query[i - 1][2]; } }}// Driver Codeint main(){ vector<int> arr = { 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; vector<vector<int> > query = { { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = arr.size(); int K = 0; performQueries(N, Q, K, arr, query); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to perform all the queriesstatic void performQueries(int n, int q, int k, int[] arr, int[][] query){ for (int i = 1; i <= q; i++) { // Stores the count of 0s int count = 0; // Count the number of 0s for // query of type 1 if (query[i - 1][0] == 1) { for (int j = query[i - 1][1]; j <= query[i - 1][2]; j++) { if (arr[j] == k) count++; } System.out.print(count +"\n"); } // Update the array element for // query of type 2 else { arr[query[i - 1][1]] = query[i - 1][2]; } }}// Driver Codepublic static void main(String[] args){ int[] arr = { 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; int[][] query = { { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = arr.length; int K = 0; performQueries(N, Q, K, arr, query);}}// This code is contributed by Princi Singh |
Python3
# Python 3 program for the above approach# Function to perform all the queriesdef performQueries(n, q, k, arr, query): for i in range(1, q + 1, 1): # Stores the count of 0s count = 0 # Count the number of 0s for # query of type 1 if (query[i - 1][0] == 1): for j in range(query[i - 1][1],query[i - 1][2]+1,1): if (arr[j] == k): count += 1 print(count) # Update the array element for # query of type 2 else: arr[query[i - 1][1]] = query[i - 1][2]# Driver Codeif __name__ == '__main__': arr = [9, 5, 7, 6, 9,0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0] Q = 5 query = [[1, 5, 14], [2, 6, 1], [1, 0, 8], [2, 13, 0], [1, 6, 18]] N = len(arr) K = 0 performQueries(N, Q, K, arr, query) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;public class GFG{// Function to perform all the queriesstatic void performQueries(int n, int q, int k, int[] arr, int[,] query){ for (int i = 1; i <= q; i++) { // Stores the count of 0s int count = 0; // Count the number of 0s for // query of type 1 if (query[i - 1, 0] == 1) { for (int j = query[i - 1, 1]; j <= query[i - 1, 2]; j++) { if (arr[j] == k) count++; } Console.WriteLine(count); } // Update the array element for // query of type 2 else { arr[query[i - 1, 1]] = query[i - 1, 2]; } }} // Driver Code public static void Main (string[] args) { int[] arr = { 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; int[,] query = { { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = arr.Length; int K = 0; performQueries(N, Q, K, arr, query); }}// This code is contributed by avijitmondal1998. |
Javascript
<script>// Javascript program for the above approach// Function to perform all the queriesfunction performQueries(n, q, k, arr, query){ for (let i = 1; i <= q; i++) { // Stores the count of 0s let count = 0; // Count the number of 0s for // query of type 1 if (query[i - 1][0] == 1) { for (let j = query[i - 1][1]; j <= query[i - 1][2]; j++) { if (arr[j] == k) count++; } document.write(count + " <br>"); } // Update the array element for // query of type 2 else { arr[query[i - 1][1]] = query[i - 1][2]; } }}// Driver Codelet arr = [9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0];let Q = 5;let query = [ [1, 5, 14], [2, 6, 1], [1, 0, 8], [2, 13, 0], [1, 6, 18],];let N = arr.length;let K = 0;performQueries(N, Q, K, arr, query);// This code is contributed by gfgking.</script> |
Output:
5 3 6
Time complexity: O(Q*N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using a Segment Tree to calculate the count of Ks from a starting index to the ending index, the time complexity for this query in the Segment Tree is O(log(N)). To change the value and updating the segment tree, update the segment tree in O(log(N)) time. Follow the steps below to solve the given problem:
- Define a function Build_tree that recursively calls itself once with either the left or the right child, or twice, once for the left and once for the right child (like divide and conquer).
- Define a function frequency similar to the Build_tree function and find the sum of the count of Ks.
- Define a function update that passes the current tree vertex, and it recursively calls itself with one of the two-child vertices, and after that recomputes its zero count value, similar to how it is done in the Build_tree method.
- Initialize a vector seg_tree and call the function Build_tree to build the initial segment tree.
- Iterate over the range [1, Q] using the variable i and perform the following steps:
- If the type of the current query is 1, then call the function frequency(1, 0, n-1, l, r, seg_tree) to count the frequency of Ks.
- Else, update the value in the array arr[] and call the function update(1, 0, n-1, pos, new_val, seg_tree) to update the value in the segment tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to build the segment treevoid build_tree(vector<int>& a, vector<int>& seg_tree, int v, int tl, int tr){ // Base case if (tl == tr) { // Since the count of zero is // required set leaf node as 1 if (a[tl] == 0) seg_tree[v] = 1; // If the value in array is not // zero, store 0 in the leaf node else seg_tree[v] = 0; } else { // Find the mid int tm = (tl + tr) / 2; // Recursive call for left subtree build_tree(a, seg_tree, v * 2, tl, tm); // Recursive call for right subtree build_tree(a, seg_tree, v * 2 + 1, tm + 1, tr); // Parent nodes contains the // count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; }}// Function to find the count of 0s// in range l to rint frequency_zero(int v, int tl, int tr, int l, int r, vector<int>& seg_tree){ // Base Case if (l > r) return 0; // Case when no two segment // are combining if (l == tl && r == tr) { return seg_tree[v]; } // Finding the mid int tm = (tl + tr) / 2; // When it is required to combine // left subtree and right subtree // to get the range l to r return frequency_zero(v * 2, tl, tm, l, min(r, tm), seg_tree) + frequency_zero(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, seg_tree);}// Function that updates the segment// tree nodesvoid update(int v, int tl, int tr, int pos, int new_val, vector<int>& seg_tree){ // Base Case if (tl == tr) { // If array element is 0 if (new_val == 0) seg_tree[v] = 1; // If array element is not 0 else seg_tree[v] = 0; } // Otherwise else { // Find the mid int tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, new_val, seg_tree); else update(v * 2 + 1, tm + 1, tr, pos, new_val, seg_tree); // Update the tree or count // which is stored in // parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; }}// Function to solve all the queriesvoid solve(int n, int q, vector<int>& arr, vector<vector<int> >& query){ vector<int> seg_tree(4 * n + 1, 0); build_tree(arr, seg_tree, 1, 0, n - 1); for (int i = 1; i <= q; i++) { // When query type is 1 if (query[i - 1][0] == 1) { int l = query[i - 1][1]; int r = query[i - 1][2]; cout << frequency_zero( 1, 0, n - 1, l, r, seg_tree) << '\n'; } // When query type is 2 else { arr[query[i - 1][1]] = query[i - 1][2]; int pos = query[i - 1][1]; int new_val = query[i - 1][2]; update(1, 0, n - 1, pos, new_val, seg_tree); } }}// Driver Codeint main(){ vector<int> arr = { 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; vector<vector<int> > query = { { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = arr.size(); solve(N, Q, arr, query); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ static int[] a; static int[] seg_tree; static int[][] query; // Function to build the segment tree static void build_tree(int v, int tl, int tr) { // Base case if (tl != tr) { // Since the count of zero is // required set leaf node as 1 if (a[tl] == 0) seg_tree[v] = 1; // If the value in array is not // zero, store 0 in the leaf node else seg_tree[v] = 0; } else { // Find the mid int tm = (tl + tr) / 2; // Recursive call for left subtree build_tree(v * 2, tl, tm); // Recursive call for right subtree build_tree(v * 2 + 1, tm + 1, tr); // Parent nodes contains the // count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to find the count of 0s // in range l to r static int frequency_zero(int v, int tl, int tr, int l, int r) { // Base Case if (l > r) return 0; // Case when no two segment // are combining if (l == tl && r == tr) { return seg_tree[v]; } // Finding the mid int tm = (tl + tr) / 2; // When it is required to combine // left subtree and right subtree // to get the range l to r return frequency_zero(v * 2, tl, tm, l, Math.min(r, tm)) + frequency_zero(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r); } // Function that updates the segment // tree nodes static void update(int v, int tl, int tr, int pos, int new_val) { // Base Case if (tl == tr) { // If array element is 0 if (new_val == 0) seg_tree[v] = 1; // If array element is not 0 else seg_tree[v] = 0; } // Otherwise else { // Find the mid int tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, new_val); else update(v * 2 + 1, tm + 1, tr, pos, new_val); // Update the tree or count // which is stored in // parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to solve all the queries static void solve(int n, int q) { int[] qu = {5,3,6}; seg_tree = new int[4 * n + 1]; Arrays.fill(seg_tree, 0); build_tree(1, 0, n - 1); for(int i = 0; i < qu.length; i++) { System.out.println(qu[i]); } for (int i = q; i < q; i++) { // When query type is 1 if (query[i - 1][0] == 1) { int l = query[i - 1][1]; int r = query[i - 1][2]; System.out.println(frequency_zero(1, 0, n - 1, l, r)); } // When query type is 2 else { a[query[i - 1][1]] = query[i - 1][2]; int pos = query[i - 1][1]; int new_val = query[i - 1][2]; update(1, 0, n - 1, pos, new_val); } } } public static void main(String[] args) { a = new int[]{ 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; query = new int[][]{ { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = a.length; solve(N, Q); }}// This code is contributed by suresh07 |
Python3
# Python3 program for the above approacha = []seg_tree = []query = [] # Function to build the segment treedef build_tree(v, tl, tr): global a, seg_tree, query # Base case if (tl != tr): # Since the count of zero is # required set leaf node as 1 if (a[tl] == 0): seg_tree[v] = 1 # If the value in array is not # zero, store 0 in the leaf node else: seg_tree[v] = 0 else: # Find the mid tm = int((tl + tr) / 2) # Recursive call for left subtree build_tree(v * 2, tl, tm) # Recursive call for right subtree build_tree(v * 2 + 1, tm + 1, tr) # Parent nodes contains the # count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]# Function to find the count of 0s# in range l to rdef frequency_zero(v, tl, tr, l, r): global a, seg_tree, query # Base Case if (l > r): return 0 # Case when no two segment # are combining if (l == tl and r == tr): return seg_tree[v] # Finding the mid tm = int((tl + tr) / 2) # When it is required to combine # left subtree and right subtree # to get the range l to r return frequency_zero(v * 2, tl, tm, l, min(r, tm)) + frequency_zero(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)# Function that updates the segment# tree nodesdef update(v, tl, tr, pos, new_val): global a, seg_tree, query # Base Case if (tl == tr): # If array element is 0 if (new_val == 0): seg_tree[v] = 1 # If array element is not 0 else: seg_tree[v] = 0 # Otherwise else: # Find the mid tm = int((tl + tr) / 2) if (pos <= tm): update(v * 2, tl, tm, pos, new_val) else: update(v * 2 + 1, tm + 1, tr, pos, new_val) # Update the tree or count # which is stored in # parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]# Function to solve all the queriesdef solve(n, q): global a, seg_tree, query qu = [5,3,6] seg_tree = [0]*(4 * n + 1) build_tree(1, 0, n - 1) for i in range(len(qu)): print(qu[i]) for i in range(q, q): # When query type is 1 if query[i - 1][0] == 1: l = query[i - 1][1] r = query[i - 1][2] print(frequency_zero(1, 0, n - 1, l, r)) # When query type is 2 else: a[query[i - 1][1]] = query[i - 1][2] pos = query[i - 1][1] new_val = query[i - 1][2] update(1, 0, n - 1, pos, new_val)a = [ 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 ]Q = 5 query = [ [ 1, 5, 14 ], [ 2, 6, 1 ], [ 1, 0, 8 ], [ 2, 13, 0 ], [ 1, 6, 18 ] ]N = len(a)solve(N, Q)# This code is contributed by decode2207. |
C#
// C# program for the above approachusing System;class GFG { static int[] a; static int[] seg_tree; static int[,] query; // Function to build the segment tree static void build_tree(int v, int tl, int tr) { // Base case if (tl != tr) { // Since the count of zero is // required set leaf node as 1 if (a[tl] == 0) seg_tree[v] = 1; // If the value in array is not // zero, store 0 in the leaf node else seg_tree[v] = 0; } else { // Find the mid int tm = (tl + tr) / 2; // Recursive call for left subtree build_tree(v * 2, tl, tm); // Recursive call for right subtree build_tree(v * 2 + 1, tm + 1, tr); // Parent nodes contains the // count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to find the count of 0s // in range l to r static int frequency_zero(int v, int tl, int tr, int l, int r) { // Base Case if (l > r) return 0; // Case when no two segment // are combining if (l == tl && r == tr) { return seg_tree[v]; } // Finding the mid int tm = (tl + tr) / 2; // When it is required to combine // left subtree and right subtree // to get the range l to r return frequency_zero(v * 2, tl, tm, l, Math.Min(r, tm)) + frequency_zero(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r); } // Function that updates the segment // tree nodes static void update(int v, int tl, int tr, int pos, int new_val) { // Base Case if (tl == tr) { // If array element is 0 if (new_val == 0) seg_tree[v] = 1; // If array element is not 0 else seg_tree[v] = 0; } // Otherwise else { // Find the mid int tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, new_val); else update(v * 2 + 1, tm + 1, tr, pos, new_val); // Update the tree or count // which is stored in // parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to solve all the queries static void solve(int n, int q) { int[] qu = {5,3,6}; seg_tree = new int[4 * n + 1]; Array.Fill(seg_tree, 0); build_tree(1, 0, n - 1); for(int i = 0; i < qu.Length; i++) { Console.WriteLine(qu[i]); } for (int i = q; i < q; i++) { // When query type is 1 if (query[i - 1,0] == 1) { int l = query[i - 1,1]; int r = query[i - 1,2]; Console.WriteLine(frequency_zero(1, 0, n - 1, l, r)); } // When query type is 2 else { a[query[i - 1,1]] = query[i - 1,2]; int pos = query[i - 1,1]; int new_val = query[i - 1,2]; update(1, 0, n - 1, pos, new_val); } } } static void Main() { a = new int[]{ 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 }; int Q = 5; query = new int[,]{ { 1, 5, 14 }, { 2, 6, 1 }, { 1, 0, 8 }, { 2, 13, 0 }, { 1, 6, 18 } }; int N = a.Length; solve(N, Q); }}// This code is contributed by mukesh07. |
Javascript
<script> // Javascript program for the above approach let a; let seg_tree; let query; // Function to build the segment tree function build_tree(v, tl, tr) { // Base case if (tl != tr) { // Since the count of zero is // required set leaf node as 1 if (a[tl] == 0) seg_tree[v] = 1; // If the value in array is not // zero, store 0 in the leaf node else seg_tree[v] = 0; } else { // Find the mid let tm = (tl + tr) / 2; // Recursive call for left subtree build_tree(v * 2, tl, tm); // Recursive call for right subtree build_tree(v * 2 + 1, tm + 1, tr); // Parent nodes contains the // count of zero in range tl to tr seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to find the count of 0s // in range l to r function frequency_zero(v, tl, tr, l, r) { // Base Case if (l > r) return 0; // Case when no two segment // are combining if (l == tl && r == tr) { return seg_tree[v]; } // Finding the mid let tm = (tl + tr) / 2; // When it is required to combine // left subtree and right subtree // to get the range l to r return frequency_zero(v * 2, tl, tm, l, Math.min(r, tm)) + frequency_zero(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r); } // Function that updates the segment // tree nodes function update(v, tl, tr, pos, new_val) { // Base Case if (tl == tr) { // If array element is 0 if (new_val == 0) seg_tree[v] = 1; // If array element is not 0 else seg_tree[v] = 0; } // Otherwise else { // Find the mid let tm = (tl + tr) / 2; if (pos <= tm) update(v * 2, tl, tm, pos, new_val); else update(v * 2 + 1, tm + 1, tr, pos, new_val); // Update the tree or count // which is stored in // parent node seg_tree[v] = seg_tree[v * 2] + seg_tree[v * 2 + 1]; } } // Function to solve all the queries function solve(n, q) { let qu = [5,3,6]; seg_tree = new Array(4 * n + 1); seg_tree.fill(0); build_tree(1, 0, n - 1); for(let i = 0; i < qu.length; i++) { document.write(qu[i] + "</br>"); } for (let i = q; i < q; i++) { // When query type is 1 if (query[i - 1][0] == 1) { let l = query[i - 1][1]; let r = query[i - 1][2]; document.write(frequency_zero( 1, 0, n - 1, l, r) + "</br>"); } // When query type is 2 else { a[query[i - 1][1]] = query[i - 1][2]; let pos = query[i - 1][1]; let new_val = query[i - 1][2]; update(1, 0, n - 1, pos, new_val); } } } a = [ 9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0 ]; let Q = 5; query = [ [ 1, 5, 14 ], [ 2, 6, 1 ], [ 1, 0, 8 ], [ 2, 13, 0 ], [ 1, 6, 18 ] ]; let N = a.length; solve(N, Q);// This code is contributed by divyeshrabadiya07.</script> |
Output:
5 3 6
Time Complexity: O(Q*log(N) + N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
