Given an array arr[] of size N and a matrix Q consisting of queries of the following two types:
- 1 L R : Print the number of elements lying in the range [L, R].
- 2 i x : Set arr[i] = x
Examples:
Input: arr[] = {1, 2, 2, 3, 4, 4, 5, 6}, Q = {{1, {3, 5}}, {1, {2, 4}}, {1, {1, 2}}, {2, {1, 7}}, {1, {1, 2}}}
Output: 4 5 3 2
Explanation:
Array elements from the range [3, 5] are {3, 4, 4, 5}
Array elements from the range [2, 4] are {2, 2, 3, 4, 4}
Array elements from the range [1, 2] are {1, 2, 2}
Replacing arr[1] by 7 modifies the array to {1, 7, 2, 3, 4, 4, 5, 6}
Elements that lie in range [1, 2] are {1, 2}Input: arr = {5, 5, 1, 3, 4, 4, 2, 3}, Q = {{1, {3, 6}}, {1, {2, 4}}, {1, {10, 20}}}
Output: 6 5 0
Explanation:
Array elements from the range [3, 6] are {3, 3, 4, 4, 5, 5}
Array elements from the range [2, 4] are {2, 3, 3, 4, 4}
No element from the range [10, 20] exists in the array.
Naive Approach:
The simplest approach to solve this problem is as follows:
- For the query of type (1 L R), iterate over the entire array and count the number of elements in the array such that L ? arr[i] ? R. Finally, print the count.
- For the query of type (2 i x), replace arr[i] by x.
Below is the implementation of the above approach:
C++
// C++ code for queries for number // of elements that lie in range // [l, r] (with updates) #include <bits/stdc++.h> using namespace std; // Function to set arr[index] = x void setElement(int* arr, int n, int index, int x) { arr[index] = x; } // Function to get count of elements // that lie in range [l, r] int getCount(int* arr, int n, int l, int r) { int count = 0; // Traverse array for (int i = 0; i < n; i++) { // If element lies in the // range [L, R] if (arr[i] >= l && arr[i] <= r) { // Increase count count++; } } return count; } // Function to solve each query void SolveQuery(int arr[], int n, vector<pair<int, pair<int, int> > > Q) { int x; for (int i = 0; i < Q.size(); i++) { if (Q[i].first == 1) { x = getCount(arr, n, Q[i].second.first, Q[i].second.second); cout << x << " "; } else { setElement(arr, n, Q[i].second.first, Q[i].second.second); } } } // Driver Code int main() { int arr[] = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); vector<pair<int, pair<int, int> > > Q = { { 1, { 3, 5 } }, { 1, { 2, 4 } }, { 1, { 1, 2 } }, { 2, { 1, 7 } }, { 1, { 1, 2 } } }; SolveQuery(arr, n, Q); return 0; } |
Java
// Java code for queries for number // of elements that lie in range // [l, r] (with updates) import java.util.*;import java.lang.*;class GFG{ // Function to set arr[index] = xstatic void setElement(int[] arr, int n, int index, int x){ arr[index] = x;}// Function to get count of elements// that lie in range [l, r]static int getCount(int[] arr, int n, int l, int r){ int count = 0; // Traverse array for(int i = 0; i < n; i++) { // If element lies in the // range [L, R] if (arr[i] >= l && arr[i] <= r) { // Increase count count++; } } return count;}// Function to solve each querystatic void SolveQuery(int arr[], int n, ArrayList<List<Integer>> Q){ int x; for(int i = 0; i < Q.size(); i++) { if (Q.get(i).get(0) == 1) { x = getCount(arr, n, Q.get(i).get(1), Q.get(i).get(2)); System.out.print(x + " "); } else { setElement(arr, n, Q.get(i).get(1), Q.get(i).get(2)); } }} // Driver codepublic static void main (String[] args){ int arr[] = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = arr.length; ArrayList<List<Integer>> Q = new ArrayList<>(); Q.add(Arrays.asList(1, 3, 5)); Q.add(Arrays.asList(1, 2, 4)); Q.add(Arrays.asList(1, 1, 2)); Q.add(Arrays.asList(2, 1, 7)); Q.add(Arrays.asList(1, 1, 2)); SolveQuery(arr, n, Q);}}// This code is contributed by offbeat |
Python3
# Python3 code for queries for number# of elements that lie in range# [l, r] (with updates)from typing import Generic, List, TypeVarT = TypeVar('T')V = TypeVar('V')class Pair(Generic[V, T]): def __init__(self, first: V, second: T) -> None: self.first = first self.second = second# Function to set arr[index] = xdef setElement(arr: List[int], n: int, index: int, x: int) -> None: arr[index] = x# Function to get count of elements# that lie in range [l, r]def getCount(arr: List[int], n: int, l: int, r: int) -> int: count = 0 # Traverse array for i in range(n): # If element lies in the # range [L, R] if (arr[i] >= l and arr[i] <= r): # Increase count count += 1 return count# Function to solve each querydef SolveQuery(arr: List[int], n: int, Q: List[Pair[int, Pair[int, int]]]): x = 0 for i in range(len(Q)): if (Q[i].first == 1): x = getCount(arr, n, Q[i].second.first, Q[i].second.second) print(x, end = " ") else: setElement(arr, n, Q[i].second.first, Q[i].second.second)# Driver Codeif __name__ == "__main__": arr = [ 1, 2, 2, 3, 4, 4, 5, 6 ] n = len(arr) Q = [ Pair(1, Pair(3, 5)), Pair(1, Pair(2, 4)), Pair(1, Pair(1, 2)), Pair(2, Pair(1, 7)), Pair(1, Pair(1, 2)) ] SolveQuery(arr, n, Q)# This code is contributed by sanjeev2552 |
C#
// C# code for queries for number// of elements that lie in range// [l, r] (with updates)using System;using System.Collections.Generic;class GFG{// Function to set arr[index] = xstatic void setElement(int[] arr, int n, int index, int x){ arr[index] = x;}// Function to get count of elements// that lie in range [l, r]static int getCount(int[] arr, int n, int l, int r){ int count = 0; // Traverse array for(int i = 0; i < n; i++) { // If element lies in the // range [L, R] if (arr[i] >= l && arr[i] <= r) // Increase count count += 1; } return count;}// Function to solve each querystatic void SolveQuery(int[] arr, int n, List<List<int>> Q){ int x; for(int i = 0; i < Q.Count; i++) { if (Q[i][0] == 1) { x = getCount(arr, n, Q[i][1], Q[i][2]); Console.Write(x + " "); } else { setElement(arr, n, Q[i][1], Q[i][2]); } }}// Driver codepublic static void Main(string[] args){ int[] arr = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = arr.Length; List<List<int>> myList = new List<List<int>>(); myList.Add(new List<int>{ 1, 3, 5 }); myList.Add(new List<int>{ 1, 2, 4 }); myList.Add(new List<int>{ 1, 1, 2 }); myList.Add(new List<int>{ 2, 1, 7 }); myList.Add(new List<int>{ 1, 1, 2 }); SolveQuery(arr, n, myList);}}// This code is contributed by grand_master |
Javascript
<script>// Javascript code for queries for number// of elements that lie in range// [l, r] (with updates)// Function to set arr[index] = xfunction setElement(arr, n, index, x){ arr[index] = x;}// Function to get count of elements// that lie in range [l, r]function getCount(arr, n, l, r){ let count = 0; // Traverse array for (let i = 0; i < n; i++) { // If element lies in the // range [L, R] if (arr[i] >= l && arr[i] <= r) { // Increase count count++; } } return count;}// Function to solve each queryfunction SolveQuery(arr, n, Q) { let x; for (let i = 0; i < Q.length; i++) { if (Q[i][0] == 1) { x = getCount(arr, n, Q[i][1][0], Q[i][1][1]); document.write(x + " "); } else { setElement(arr, n, Q[i][1][0], Q[i][1][1]); } }}// Driver Codelet arr = [ 1, 2, 2, 3, 4, 4, 5, 6 ];let n = arr.length;let Q = [[1, [3, 5]], [1, [2, 4]], [1, [1, 2]], [2, [1, 7]], [1, [1, 2]]];SolveQuery(arr, n, Q);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
4 5 3 2
Time Complexity: O(Q * N)
Auxiliary Space: O(1)
Efficient Approach:
The above approach can be optimized using Fenwick Tree. Follow the steps below to solve the problem:
- Construct a Fenwick tree from the given array.
- Fenwick tree will be represented as an array of size equal to maximum element in the array, so that the array elements can be used as index (idea is similar to this approach).
- Traverse the array and increase the frequency of every element by calling the update method of Fenwick tree.
- For each query of type (1 L R), call the getSum method of Fenwick tree. The answer for the query of type 1 will be:
getSum(R) – getSum(L – 1)
- For each query of type (2 i x), call the update method of Fenwick tree to increase the frequency of the added element and decrease the count of the element to be replaced.
Below is the implementation of the above approach:
C++
// C++ code for queries for number // of elements that lie in range // [l, r] (with updates) #include <bits/stdc++.h> using namespace std; class FenwickTree { public: int* BIT; int N; FenwickTree(int N) { this->N = N; BIT = new int[N]; for (int i = 0; i < N; i++) { BIT[i] = 0; } } // Traverse all ancestors and // increase frequency of index void update(int index, int increment) { while (index < N) { // Increase count of the current // node of BIT Tree BIT[index] += increment; // Update index to that of parent // in update View index += (index & -index); } } // Function to return the // sum of arr[0..index] int getSum(int index) { int sum = 0; // Traverse ancestors of // BITree[index] while (index > 0) { // Add current element of // BITree to sum sum += BIT[index]; // Move index to parent node in // getSum View index -= (index & -index); } return sum; } }; // Function to set arr[index] = x void setElement(int* arr, int n, int index, int x, FenwickTree* fenTree) { int removedElement = arr[index]; fenTree->update(removedElement, -1); arr[index] = x; fenTree->update(x, 1); } // Function to get count of // elements that lie in // range [l, r] int getCount(int* arr, int n, int l, int r, FenwickTree* fenTree) { int count = fenTree->getSum(r) - fenTree->getSum(l - 1); return count; } // Function to solve each query void SolveQuery(int arr[], int n, vector<pair<int, pair<int, int> > > Q) { int N = 100001; FenwickTree* fenTree = new FenwickTree(N); for (int i = 0; i < n; i++) { fenTree->update(arr[i], 1); } int x; for (int i = 0; i < Q.size(); i++) { if (Q[i].first == 1) { x = getCount(arr, n, Q[i].second.first, Q[i].second.second, fenTree); cout << x << " "; } else { setElement(arr, n, Q[i].second.first, Q[i].second.second, fenTree); } } } // Driver Code int main() { int arr[] = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); vector<pair<int, pair<int, int> > > Q = { { 1, { 3, 5 } }, { 1, { 2, 4 } }, { 1, { 1, 2 } }, { 2, { 1, 7 } }, { 1, { 1, 2 } } }; SolveQuery(arr, n, Q); return 0; } //code contributed by dhanshriborse |
Java
// Java code for queries for number// of elements that lie in range// [l, r] (with updates)import java.util.*;class FenwickTree { int N; int[] BIT; public FenwickTree(int N) { this.N = N; BIT = new int[N]; } public void update(int index, int increment) { while (index < N) { BIT[index] += increment; index += index & -index; } } public int getSum(int index) { int sum = 0; while (index > 0) { sum += BIT[index]; index -= index & -index; } return sum; }}public class Main { // Function to return the sum of arr[0..index] public static void setElement(int[] arr, int n, int index, int x, FenwickTree fenTree) { int removedElement = arr[index]; fenTree.update(removedElement, -1); arr[index] = x; fenTree.update(x, 1); } // Function to get count of elements that lie in range // [l, r] public static int getCount(int[] arr, int n, int l, int r, FenwickTree fenTree) { int count = fenTree.getSum(r) - fenTree.getSum(l - 1); return count; } // Function to solve each query public static void SolveQuery(int[] arr, int n, ArrayList<int[]> Q) { int N = 100001; FenwickTree fenTree = new FenwickTree(N); for (int i = 0; i < n; i++) { fenTree.update(arr[i], 1); } for (int i = 0; i < Q.size(); i++) { if (Q.get(i)[0] == 1) { int x = getCount(arr, n, Q.get(i)[1], Q.get(i)[2], fenTree); System.out.print(x + " "); } else { setElement(arr, n, Q.get(i)[1], Q.get(i)[2], fenTree); } } } public static void main(String[] args) { int[] arr = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = arr.length; ArrayList<int[]> Q = new ArrayList<>(); Q.add(new int[] { 1, 3, 5 }); Q.add(new int[] { 1, 2, 4 }); Q.add(new int[] { 1, 1, 2 }); Q.add(new int[] { 2, 1, 7 }); Q.add(new int[] { 1, 1, 2 }); SolveQuery(arr, n, Q); }}// Contributed by adityasharmadev01 |
Python3
# Python code for queries for number # of elements that lie in range # [l, r] (with updates) import bisectclass FenwickTree: def __init__(self, N): self.N = N self.BIT = [0]*N def update(self, index, increment): while index < self.N: self.BIT[index] += increment index += index & -index #Traverse all ancestors and #increase frequency of index def getSum(self, index): sum = 0 while index > 0: #Increase count of the current #node of BIT Tree sum += self.BIT[index] # Update index to that of parent #in update View index -= index & -index return sum# Function to return the #sum of arr[0..index]def setElement(arr, n, index, x, fenTree): removedElement = arr[index] fenTree.update(removedElement, -1) arr[index] = x fenTree.update(x, 1)#Function to get count of #elements that lie in #range [l, r] def getCount(arr, n, l, r, fenTree): count = fenTree.getSum(r) - fenTree.getSum(l - 1) return count#Function to solve each query def SolveQuery(arr, n, Q): N = 100001 fenTree = FenwickTree(N) for i in range(n): fenTree.update(arr[i], 1) for i in range(len(Q)): if Q[i][0] == 1: x = getCount(arr, n, Q[i][1][0], Q[i][1][1], fenTree) print(x, end=" ") else: setElement(arr, n, Q[i][1][0], Q[i][1][1], fenTree)arr = [1, 2, 2, 3, 4, 4, 5, 6]n = len(arr)Q = [ (1, (3, 5)), (1, (2, 4)), (1, (1, 2)), (2, (1, 7)), (1, (1, 2))]SolveQuery(arr, n, Q)#COde contributed by dhanshriborse |
C#
// C# code for queries for number// of elements that lie in range// [l, r] (with updates)using System;using System.Collections.Generic;// FenwickTree class definitionpublic class FenwickTree{ int N; int[] BIT; // Constructor public FenwickTree(int N) { this.N = N; BIT = new int[N]; } // Update method public void update(int index, int increment) { while (index < N) { BIT[index] += increment; index += index & -index; } } // Method to get the sum of the tree // in O(logn) time public int getSum(int index) { int sum = 0; while (index > 0) { sum += BIT[index]; index -= index & -index; } return sum; }}class GFG{ // Function to return the sum of arr[0..index] public static void setElement(int[] arr, int n, int index, int x, FenwickTree fenTree) { int removedElement = arr[index]; fenTree.update(removedElement, -1); arr[index] = x; fenTree.update(x, 1); } // Function to get count of elements that lie in range // [l, r] public static int getCount(int[] arr, int n, int l, int r, FenwickTree fenTree) { int count = fenTree.getSum(r) - fenTree.getSum(l - 1); return count; } // Function to solve each query public static void SolveQuery(int[] arr, int n, List<int[]> Q) { int N = 100001; FenwickTree fenTree = new FenwickTree(N); for (int i = 0; i < n; i++) { fenTree.update(arr[i], 1); } for (int i = 0; i < Q.Count; i++) { if (Q[i][0] == 1) { int x = getCount(arr, n, Q[i][1], Q[i][2], fenTree); Console.Write(x + " "); } else { setElement(arr, n, Q[i][1], Q[i][2], fenTree); } } } // Driver code public static void Main(string[] args) { int[] arr = { 1, 2, 2, 3, 4, 4, 5, 6 }; int n = arr.Length; List<int[]> Q = new List<int[] >(); Q.Add(new int[] { 1, 3, 5 }); Q.Add(new int[] { 1, 2, 4 }); Q.Add(new int[] { 1, 1, 2 }); Q.Add(new int[] { 2, 1, 7 }); Q.Add(new int[] { 1, 1, 2 }); // Function call SolveQuery(arr, n, Q); }} |
Javascript
// Define the FenwickTree classclass FenwickTree { constructor(N) { this.N = N; this.BIT = new Array(N).fill(0); } // Update the value of the given index with the given increment update(index, increment) { while (index < this.N) { this.BIT[index] += increment; // Update the index to its parent node in the BIT tree index += index & -index; } } // Get the sum of values up to the given index getSum(index) { let sum = 0; while (index > 0) { // Increase the count of the current node of the BIT tree sum += this.BIT[index]; // Update the index to its parent node in the update view index -= index & -index; } return sum; }}// Set the value of the element at the given index // to the given value, and update the Fenwick tree accordinglyfunction setElement(arr, n, index, x, fenTree) { let removedElement = arr[index]; fenTree.update(removedElement, -1); arr[index] = x; fenTree.update(x, 1);}// Get the count of elements in the given array // that lie in the range [l, r] using the Fenwick treefunction getCount(arr, n, l, r, fenTree) { let count = fenTree.getSum(r) - fenTree.getSum(l - 1); return count;}// Solve each query in the given array of queriesfunction SolveQuery(arr, n, Q) { let N = 100001; let fenTree = new FenwickTree(N); // Initialize the Fenwick tree with the values in the array for (let i = 0; i < n; i++) { fenTree.update(arr[i], 1); } // Process each query in the array for (let i = 0; i < Q.length; i++) { if (Q[i][0] == 1) { // If the query is of type 1, get the count of elements in the range [l, r] let x = getCount(arr, n, Q[i][1][0], Q[i][1][1], fenTree); // Print the count to the console process.stdout.write(x + " "); } else { // If the query is of type 2, update the value of an element in the array setElement(arr, n, Q[i][1][0], Q[i][1][1], fenTree); } }}// Define the input array and the array of querieslet arr = [1, 2, 2, 3, 4, 4, 5, 6];let n = arr.length;let Q = [ [1, [3, 5]], [1, [2, 4]], [1, [1, 2]], [2, [1, 7]], [1, [1, 2]],];// Call the SolveQuery function with // the input array and the array of queriesSolveQuery(arr, n, Q); |
Output:
4 5 3 2
Time Complexity: O(n*log(N) + Q*log(N))
Auxiliary Space: O(maxm), where maxm is the maximum element present in the array.
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!
