Count of possible remainders for K in given ranges for Q queries
Given an array arr[ ] which contains N positive integers and an integer K and a vector of queries Q . Two types of queries can be asked:
- In the type 1 query, all elements from index l to r are increased by value X. The input format of this query: 1 l r x
- In the type 2 query, for a given integer K print the count of all possible remainders if elements from index l to r are divided by k. The input format of this query: 2 l r
Examples:
Input: arr[ ] = {7, 13, 5, 9, 16, 21}, K=4, vector< vector< int > >Q = { {2, 3, 5}, { 1, 0, 4, 1}, {2, 2, 5} }
Output: 1 2 0 0
0 2 2 0
Explanation: The first query type is 2. so, for index 3 to 5, there is only one element => ( 16 ) whose remainder is 0 for given k=4. Two elements whose remainder is 1 => ( 9, 21 ). There is no element whose remainder is 2 or 3.
After second query arr will be: {8, 14, 6, 10, 17, 21} . because of all array elements are increased by 1 .
In the third query for index 2 to 5, there are two elements whose remainders are 1 (17, 21) and 2 (6, 10). There is no elements whose remainder is 0 or 3.Input: arr[ ] = {6, 7, 8, 9, 10, 11}, k=5, vector< vector< int > >Q = { {2, 1, 1 } {2, 1, 3}, { 1, 1, 3, 2}, {2, 1, 3} }
Output: 0 0 1 0 0
0 0 1 1 1
1 1 0 0 1
Naive Approach: A simple approach is in update query just iterate through an array in a given range and update value. And for another type of query iterate through the given range and take mod with k, keep hash array to store particular count of that remainder. But time complexity of this method is O(N*Q*k)
Time Complexity: O(N*Q*k)
Auxiliary Space: O(k), for maintaining a hash array of size k
Efficient Approach: The above approach can be optimized using segment tree and lazy propagation, based on below idea:
Intuition:
Here numbers of queries are high and there are queries also in which a range l to r has to be updated. Also we have to print answers for the given range l to r.
So, these are giving hints to use segment tree with lazy propagation, because in this method we can answer each query in O( log(N) ) time i.e. ( Height of segment tree). Along with this, we will use lazy propagation to update the range values in an efficient manner, because in lazy propagation, we only update the node of the segment tree which is currently required and will propagate the value to the child node, and will update this child node, whenever it is required.
To store this propagate value,
- Use an array named lazy (check code) Instead of a given value,
- Just update a range with val%k, because the main focus is remainder and this will not affect the answer.
- Use a 2D segment tree, so that each node of the segment tree contains an array of length K, to store the count of all possible remainders.
Illustration:
For arr[]={1, 2, 5}, k=4, segment tree looks like:
so basically node segment[ ind ][ j ] will contain the count of elements whose remainder is j corresponding to a range covered by the indth index of the segment tree.
In other words, if the indth index of segment tree cover range a to b of the array then segment[ ind ][ 0 ] represents, the count of elements whose remainder is 0 in range a to b.
Similarly segment[ ind ][ j ] will represent the count of elements whose remainder is j for given K in range a to b.
Here the main trick is if any range is updated by value x, then all elements of the array of length K which is attached with the segment tree’s node, will do the right cyclic shift by x%k positions.
Suppose if any range values are increased by 1, it means count of elements whose remainder was 0 now it become count of elements whose remainder is 1.Before modifying that node, store the value in the temporary array.
After that, modify the node of the segment tree by segment[ ind ][ (val+i)%k ]=temp[ i ]
Below is the implementation of the above approach:
C++
// C++ program for Find count of all // possible remainders for given integer K // in the given ranges for Q queries. #include <bits/stdc++.h> using namespace std; #define MXX 100001 // to store propagate value int lazy[4 * MXX]; int segment[4 * MXX][51]; int ans[51]; // build segment tree for given arr void build( int arr[], int low, int high, int ind, int k) { if (low == high) { int rem = arr[low] % k; // mark 1 at ind corresponding to remainder segment[ind][rem] = 1; return ; } int mid = (low + high) >> 1; build(arr, low, mid, 2 * ind + 1, k); build(arr, mid + 1, high, 2 * ind + 2, k); // before returning, compute answer for // all possible remainders for node ind for ( int i = 0; i < k; i++) { segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i]; } } // to update a range l to r void update( int l, int r, int low, int high, int ind, int k, int val) { lazy[ind] %= k; // if any value is pending then update it if (lazy[ind] != 0) { if (low != high) { // propagate pending value to its children lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } int incr = lazy[ind]; // make temporary vector to store value // so we can perform cycle operation without // losing actual values vector< int > temp(k); for ( int i = 0; i < k; i++) { temp[i] = segment[ind][i]; } // do cyclic shift operation for ( int i = 0; i < k; i++) { segment[ind][(incr + i) % k] = temp[i]; } // after done pending update mark it 0. lazy[ind] = 0; } // invalid range then return if (high < low || low > r || high < l) return ; // the current range is subset of // our actual range so update value if (low >= l && high <= r) { val %= k; vector< int > temp(k); for ( int i = 0; i < k; i++) { temp[i] = segment[ind][i]; } for ( int i = 0; i < k; i++) { segment[ind][(val + i) % k] = temp[i]; } if (low != high) { lazy[2 * ind + 1] += val; lazy[2 * ind + 2] += val; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } return ; } int mid = (low + high) >> 1; // go to left and right side update(l, r, low, mid, 2 * ind + 1, k, val); update(l, r, mid + 1, high, 2 * ind + 2, k, val); // after updating and before returning, // calculate answer for ( int i = 0; i < k; i++) { segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i]; } } // to compute answer of a query // most of operation are same as update function void query( int l, int r, int low, int high, int ind, int k) { lazy[ind] %= k; if (lazy[ind] != 0) { if (low != high) { lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } int incr = lazy[ind]; vector< int > temp(k); for ( int i = 0; i < k; i++) { temp[i] = segment[ind][i]; } for ( int i = 0; i < k; i++) { segment[ind][(incr + i) % k] = temp[i]; } lazy[ind] = 0; } if (high < low || low > r || high < l) return ; // this range is subset of our actual // require range so compute answer for // this range if (low >= l && high <= r) { for ( int i = 0; i < k; i++) ans[i] += segment[ind][i]; return ; } int mid = (low + high) >> 1; query(l, r, low, mid, 2 * ind + 1, k); query(l, r, mid + 1, high, 2 * ind + 2, k); } // after printing answer // reset ans array void print( int k) { for ( int i = 0; i < k; i++) cout << ans[i] << " " ; cout << "\n" ; } void reset() { for ( int i = 0; i < 51; i++) ans[i] = 0; } int main() { int arr[] = { 7, 13, 5, 9, 16, 21 }; int n = sizeof (arr) / sizeof (arr[0]); int q = 3, k = 4; // build segment tree build(arr, 0, n - 1, 0, k); // first query int x, l = 3, r = 5; query(l, r, 0, n - 1, 0, k); print(k); reset(); // second query l = 0, r = 4, x = 1; update(l, r, 0, n - 1, 0, k, x); // third query l = 2, r = 5; query(l, r, 0, n - 1, 0, k); print(k); reset(); return 0; } |
Java
import java.util.*; import java.io.*; // Java program for Find count of all // possible remainders for given integer K // in the given ranges for Q queries. class GFG{ public static int MXX = 100001 ; // to store propagate value public static int lazy[] = new int [ 4 * MXX]; public static int segment[][] = new int [ 4 * MXX][ 51 ]; public static int ans[] = new int [ 51 ]; // build segment tree for given arr public static void build( int arr[], int low, int high, int ind, int k) { if (low == high) { int rem = arr[low] % k; // mark 1 at ind corresponding to remainder segment[ind][rem] = 1 ; return ; } int mid = (low + high) >> 1 ; build(arr, low, mid, 2 * ind + 1 , k); build(arr, mid + 1 , high, 2 * ind + 2 , k); // before returning, compute answer for // all possible remainders for node ind for ( int i = 0 ; i < k; i++) { segment[ind][i] = segment[ 2 * ind + 1 ][i] + segment[ 2 * ind + 2 ][i]; } } // to update a range l to r public static void update( int l, int r, int low, int high, int ind, int k, int val) { lazy[ind] %= k; // if any value is pending then update it if (lazy[ind] != 0 ) { if (low != high) { // propagate pending value to its children lazy[ 2 * ind + 1 ] += lazy[ind]; lazy[ 2 * ind + 2 ] += lazy[ind]; lazy[ 2 * ind + 1 ] %= k; lazy[ 2 * ind + 2 ] %= k; } int incr = lazy[ind]; // make temporary array to store value // so we can perform cycle operation without // losing actual values int temp[] = new int [k]; for ( int i = 0 ; i < k; i++) { temp[i] = segment[ind][i]; } // do cyclic shift operation for ( int i = 0 ; i < k; i++) { segment[ind][(incr + i) % k] = temp[i]; } // after done pending update mark it 0. lazy[ind] = 0 ; } // invalid range then return if (high < low || low > r || high < l){ return ; } // the current range is subset of // our actual range so update value if (low >= l && high <= r) { val %= k; int temp[] = new int [k]; for ( int i = 0 ; i < k; i++) { temp[i] = segment[ind][i]; } for ( int i = 0 ; i < k ; i++) { segment[ind][(val + i) % k] = temp[i]; } if (low != high) { lazy[ 2 * ind + 1 ] += val; lazy[ 2 * ind + 2 ] += val; lazy[ 2 * ind + 1 ] %= k; lazy[ 2 * ind + 2 ] %= k; } return ; } int mid = (low + high) >> 1 ; // go to left and right side update(l, r, low, mid, 2 * ind + 1 , k, val); update(l, r, mid + 1 , high, 2 * ind + 2 , k, val); // after updating and before returning, // calculate answer for ( int i = 0 ; i < k; i++) { segment[ind][i] = segment[ 2 * ind + 1 ][i] + segment[ 2 * ind + 2 ][i]; } } // to compute answer of a query // most of operation are same as update function public static void query( int l, int r, int low, int high, int ind, int k) { lazy[ind] %= k; if (lazy[ind] != 0 ) { if (low != high) { lazy[ 2 * ind + 1 ] += lazy[ind]; lazy[ 2 * ind + 2 ] += lazy[ind]; lazy[ 2 * ind + 1 ] %= k; lazy[ 2 * ind + 2 ] %= k; } int incr = lazy[ind]; int temp[] = new int [k]; for ( int i = 0 ; i < k ; i++) { temp[i] = segment[ind][i]; } for ( int i = 0 ; i < k ; i++) { segment[ind][(incr + i) % k] = temp[i]; } lazy[ind] = 0 ; } if (high < low || low > r || high < l) return ; // this range is subset of our actual // require range so compute answer for // this range if (low >= l && high <= r) { for ( int i = 0 ; i < k ; i++){ ans[i] += segment[ind][i]; } return ; } int mid = (low + high) >> 1 ; query(l, r, low, mid, 2 * ind + 1 , k); query(l, r, mid + 1 , high, 2 * ind + 2 , k); } // after printing answer // reset ans array public static void print( int k) { for ( int i = 0 ; i < k; i++) System.out.print(ans[i] + " " ); System.out.println( "" ); } public static void reset() { for ( int i = 0 ; i < 51 ; i++){ ans[i] = 0 ; } } // Driver code public static void main(String args[]) { int arr[] = { 7 , 13 , 5 , 9 , 16 , 21 }; int n = arr.length; int q = 3 , k = 4 ; // build segment tree build(arr, 0 , n- 1 , 0 , k); // first query int x, l = 3 , r = 5 ; query(l, r, 0 , n- 1 , 0 , k); print(k); reset(); // second query l = 0 ; r = 4 ; x = 1 ; update(l, r, 0 , n- 1 , 0 , k, x); // third query l = 2 ; r = 5 ; query(l, r, 0 , n- 1 , 0 , k); print(k); reset(); } } // This code is contributed by subhamgoyal2014. |
Python3
# program for Find count of all # possible remainders for given integer K # in the given ranges for Q queries. MXX = 100001 # to store propagate value lazy = [ 0 ] * ( 4 * MXX) segment = [[ 0 for i in range ( 51 )] for i in range ( 4 * MXX)] ans = [ 0 ] * 51 # build segment tree for given arr def build(arr, low, high, ind, k): if low = = high: rem = arr[low] % k # mark 1 at ind corresponding to remainder segment[ind][rem] = 1 return mid = (low + high) >> 1 build(arr, low, mid, 2 * ind + 1 , k) build(arr, mid + 1 , high, 2 * ind + 2 , k) # Before returning, compute answer for # all possible remainders for node ind for i in range (k): segment[ind][i] = segment[ 2 * ind + 1 ][i] + segment[ 2 * ind + 2 ][i] # function to update a range l to r def update(l, r, low, high, ind, k, val): lazy[ind] % = k # if any value is pending then update it if lazy[ind] ! = 0 : if low ! = high: # propagate pending value to its children lazy[ 2 * ind + 1 ] + = lazy[ind] lazy[ 2 * ind + 2 ] + = lazy[ind] lazy[ 2 * ind + 1 ] % = k lazy[ 2 * ind + 2 ] % = k incr = lazy[ind] # make temporary vector to store value # so we can perform cycle operation without # losing actual values temp = [ 0 ] * k for i in range (k): temp[i] = segment[ind][i] # do cyclic shift operation for i in range (k): segment[ind][(incr + 1 ) % k] = temp[i] # after done pending update mark it 0. lazy[ind] = 0 # invalid range then return if high < low or low > r or high < l: return # the current range is subset of # our actual range so update value if low > = l and high < = r: val % = k temp = [ 0 ] * k for i in range (k): temp[i] = segment[ind][i] for i in range (k): segment[ind][(val + i) % k] = temp[i] if low ! = high: lazy[ 2 * ind + 1 ] + = val lazy[ 2 * ind + 2 ] + = val lazy[ 2 * ind + 1 ] % = k lazy[ 2 * ind + 2 ] % = k return mid = (low + high) >> 1 # go to left and right side update(l, r, low, mid, 2 * ind + 1 , k, val) update(l, r, mid + 1 , high, 2 * ind + 2 , k, val) # after updating and before returning, calculate answer for i in range (k): segment[ind][i] = segment[ 2 * ind + 1 ][i] + segment[ 2 * ind + 2 ][i] # to compute answer of a query # most of operation are same as update function def query(l, r, low, high, ind, k): lazy[ind] % = k if lazy[ind] ! = 0 : if low ! = high: lazy[ 2 * ind + 1 ] + = lazy[ind] lazy[ 2 * ind + 2 ] + = lazy[ind] lazy[ 2 * ind + 1 ] % = k lazy[ 2 * ind + 2 ] % = k incr = lazy[ind] temp = [ 0 ] * k for i in range (k): temp[i] = segment[ind][i] for i in range (k): segment[ind][(incr + i) % k] = temp[i] lazy[ind] = 0 if high < low or low > r or high < l: return # this range is subset of our actual # require range so compute answer for # this range if low > = l and high < = r: for i in range (k): ans[i] + = segment[ind][i] return mid = (low + high) >> 1 query(l, r, low, mid, 2 * ind + 1 , k) query(l, r, mid + 1 , high, 2 * ind + 2 , k) # after printing answer # reset ans array def printing(k): for i in range ( int (k)): print (ans[i], end = " " ) print () def reset(): for i in range ( 51 ): ans[i] = 0 # Driver Code if __name__ = = '__main__' : arr = [ 7 , 13 , 5 , 9 , 16 , 21 , 33 , 12 , 19 ] n = len (arr) q = 3 k = 4 # build segment tree build(arr, 0 , n - 1 , 0 , k) # first query x = 0 l = 3 r = 5 query(l, r, 0 , n - 1 , 0 , k) printing(k) reset() # second query l = 0 r = 4 x = 1 update(l, r, 0 , n - 1 , 0 , k, x) # third query l = 2 r = 5 query(l, r, 0 , n - 1 , 0 , k) printing(k) reset() '''This Code is contributed by RAJAT KUMAR''' |
C#
// C# program for Find count of all // possible remainders for given integer K // in the given ranges for Q queries. using System; public class GFG { public static int MXX = 100001; // to store propagate value public static int [] lazy = new int [4 * MXX]; public static int [, ] segment = new int [4 * MXX, 51]; public static int [] ans = new int [51]; // build segment tree for given arr public static void build( int [] arr, int low, int high, int ind, int k) { if (low == high) { int rem = arr[low] % k; // mark 1 at ind corresponding to remainder segment[ind, rem] = 1; return ; } int mid = (low + high) >> 1; build(arr, low, mid, 2 * ind + 1, k); build(arr, mid + 1, high, 2 * ind + 2, k); // before returning, compute answer for // all possible remainders for node ind for ( int i = 0; i < k; i++) { segment[ind, i] = segment[2 * ind + 1, i] + segment[2 * ind + 2, i]; } } // to update a range l to r public static void update( int l, int r, int low, int high, int ind, int k, int val) { lazy[ind] %= k; // if any value is pending then update it if (lazy[ind] != 0) { if (low != high) { // propagate pending value to its children lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } int incr = lazy[ind]; // make temporary array to store value // so we can perform cycle operation without // losing actual values int [] temp = new int [k]; for ( int i = 0; i < k; i++) { temp[i] = segment[ind, i]; } // do cyclic shift operation for ( int i = 0; i < k; i++) { segment[ind, (incr + i) % k] = temp[i]; } // after done pending update mark it 0. lazy[ind] = 0; } // invalid range then return if (high < low || low > r || high < l) { return ; } // the current range is subset of // our actual range so update value if (low >= l && high <= r) { val %= k; int [] temp = new int [k]; for ( int i = 0; i < k; i++) { temp[i] = segment[ind, i]; } for ( int i = 0; i < k; i++) { segment[ind, (val + i) % k] = temp[i]; } if (low != high) { lazy[2 * ind + 1] += val; lazy[2 * ind + 2] += val; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } return ; } int mid = (low + high) >> 1; // go to left and right side update(l, r, low, mid, 2 * ind + 1, k, val); update(l, r, mid + 1, high, 2 * ind + 2, k, val); // after updating and before returning, // calculate answer for ( int i = 0; i < k; i++) { segment[ind, i] = segment[2 * ind + 1, i] + segment[2 * ind + 2, i]; } } // to compute answer of a query // most of operation are same as update function public static void query( int l, int r, int low, int high, int ind, int k) { lazy[ind] %= k; if (lazy[ind] != 0) { if (low != high) { lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } int incr = lazy[ind]; int [] temp = new int [k]; for ( int i = 0; i < k; i++) { temp[i] = segment[ind, i]; } for ( int i = 0; i < k; i++) { segment[ind, (incr + i) % k] = temp[i]; } lazy[ind] = 0; } if (high < low || low > r || high < l) return ; // this range is subset of our actual // require range so compute answer for // this range if (low >= l && high <= r) { for ( int i = 0; i < k; i++) { ans[i] += segment[ind, i]; } return ; } int mid = (low + high) >> 1; query(l, r, low, mid, 2 * ind + 1, k); query(l, r, mid + 1, high, 2 * ind + 2, k); } // after printing answer // reset ans array public static void print( int k) { for ( int i = 0; i < k; i++) Console.Write(ans[i] + " " ); Console.WriteLine( "" ); } public static void reset() { for ( int i = 0; i < 51; i++) { ans[i] = 0; } } static public void Main() { // Code int [] arr = { 7, 13, 5, 9, 16, 21 }; int n = arr.Length; int k = 4; // build segment tree build(arr, 0, n - 1, 0, k); // first query int x, l = 3, r = 5; query(l, r, 0, n - 1, 0, k); print(k); reset(); // second query l = 0; r = 4; x = 1; update(l, r, 0, n - 1, 0, k, x); // third query l = 2; r = 5; query(l, r, 0, n - 1, 0, k); print(k); reset(); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code for the above approach // Find count of all possible remainders // for given integer K in the given ranges // for Q queries using a segment tree let MXX = 10001; // to store propagate value let lazy = new Array(4 * MXX).fill(0); let segment = new Array(4 * MXX).fill().map(() => new Array(51).fill(0)); let ans = new Array(51).fill(0); // build segment tree for given arr function build(arr, low, high, ind, k) { if (low === high) { let rem = arr[low] % k; // mark 1 at ind corresponding to remainder segment[ind][rem] = 1; return ; } let mid = Math.floor((low + high) / 2); build(arr, low, mid, 2 * ind + 1, k); build(arr, mid + 1, high, 2 * ind + 2, k); // before returning, compute answer for // all possible remainders for node ind for (let i = 0; i < k; i++) { segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i]; } } // to update a range l to r function update(l, r, low, high, ind, k, val) { lazy[ind] %= k; // if any value is pending then update it if (lazy[ind] !== 0) { if (low !== high) { // propagate pending value to its children lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } let incr = lazy[ind]; // make temporary vector to store value // so we can perform cycle operation without // losing actual values let temp = new Array(k).fill(0); for (let i = 0; i < k; i++) { temp[i] = segment[ind][i]; } // do cyclic shift operation for (let i = 0; i < k; i++) { segment[ind][(incr + i) % k] = temp[i]; } // after done pending update mark it 0. lazy[ind] = 0; } // invalid range then return if (high < low || low > r || high < l) return ; // the current range is subset of // our actual range so update value if (low >= l && high <= r) { val %= k; let temp = new Array(k).fill(0); for (let i = 0; i < k; i++) { temp[i] = segment[ind][i]; } for (let i = 0; i < k; i++) { segment[ind][(val + i) % k] = temp[i]; } if (low !== high) { lazy[2 * ind + 1] += val; lazy[2 * ind + 2] += val; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } return ; } let mid = Math.floor((low + high) / 2); // go to left and right side update(l, r, low, mid, 2 * ind + 1, k, val); update(l, r, mid + 1, high, 2 * ind + 2, k, val); // after updating and before returning, // calculate answer for (let i = 0; i < k; i++) { segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i]; } } // to compute answer of a query // most of operation are same as update function function query(l, r, low, high, ind, k) { lazy[ind] %= k; if (lazy[ind] !== 0) { if (low !== high) { lazy[2 * ind + 1] += val; lazy[2 * ind + 2] += val; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } return ; } const mid = Math.floor((low + high) / 2); // go to left and right side update(l, r, low, mid, 2 * ind + 1, k, val); update(l, r, mid + 1, high, 2 * ind + 2, k, val); // after updating and before returning, // calculate answer for (let i = 0; i < k; i++) { segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i]; } } // to compute answer of a query // most of operation are same as update function function query(l, r, low, high, ind, k) { lazy[ind] %= k; if (lazy[ind] !== 0) { if (low !== high) { lazy[2 * ind + 1] += lazy[ind]; lazy[2 * ind + 2] += lazy[ind]; lazy[2 * ind + 1] %= k; lazy[2 * ind + 2] %= k; } const incr = lazy[ind]; const temp = new Array(k).fill(0); for (let i = 0; i < k; i++) { temp[i] = segment[ind][i]; } for (let i = 0; i < k; i++) { segment[ind][(incr + i) % k] = temp[i]; } lazy[ind] = 0; } if (high < low || low > r || high < l) return ; if (low >= l && high <= r) { for (let i = 0; i < k; i++) { ans[i] += segment[ind][i]; } return ; } const mid = Math.floor((low + high) / 2); query(l, r, low, mid, 2 * ind + 1, k); query(l, r, mid + 1, high, 2 * ind + 2, k); } // Driver code const arr = [7, 13, 5, 9, 16, 21]; const k = 4; let q = 3; let l = 3, r = 5; build(arr, 0, arr.length - 1, 0, k); query(l, r, 0, arr.length - 1, 0, k); console.log(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3] + "<br>" ); // Output: [1, 2, 0] for (let i = 0; i < 51; i++) { ans[i] = 0; } l = 0, r = 4; let x = 1 update(l, r, 0, arr.length - 1, 0, k, x); l = 2; r = 5; query(l, r, 0, arr.length - 1, 0, k); console.log(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]); // Output: [0, 2, 1] // This code is contributed by Potta Lokesh |
1 2 0 0 0 2 2 0
Time Complexity: O(Q*K*logN)
Auxiliary Space: O(N*K)