Range Minimum Query with Range Assignment
There is an array of n elements, initially filled with zeros. The task is to perform q queries from given queries[][] and there are two types of queries:
- Type 1 (i.e queries[i][0] == 1): Assign value val = queries[i][3] to all elements on the segment l = queries[i][1] to r = queries[i][2].
- Type 2 (i.e queries[i][0] == 2): Find the minimum on the segment from l = queries[i][1] to r = queries[i][2].
Example:
Input: n = 5, q = 6, queries = {
{1, 0, 3, 3},
{2, 1, 2},
{1, 1, 4, 4},
{2, 1, 3},
{2, 1, 4},
{2, 3, 5} };Output:
3
4
4
0
Approach: To solve the problem follow the below Idea.
The idea is to use a Segment Tree Data Structure, a binary tree data structure where each node represents an interval or segment of the array. The root of the tree represents the entire array, and each leaf node represents a single element of the array. This structure allows us to perform operations on a range of elements in logarithmic time.
- Build: The segment tree is built such that each node stores the minimum value in its corresponding segment of the array.
- Update: When we need to update a range of elements (query type 1), we use a technique called lazy propagation. Instead of immediately updating all the elements in the range, we mark the corresponding node in the segment tree as “lazy”. This means that the update is pending, and should be applied later when we actually need to access the elements in that range.
- Push: Before we perform an operation on a node (either an update or a query), we first “push” the pending updates to its children. This ensures that our operation is performed on up-to-date data.
- Query: To find the minimum value in a range (query type 2), we traverse the segment tree from the root to the leaves, pushing any pending updates along the way. We combine the results from the relevant nodes to obtain the minimum value in the desired range.
Steps were taken to implement the approach:
- Create the array a of size n+1, the segment tree t of size 4*n, and the lazy propagation array lazy of size 4*n.
- Call the build function to construct the initial segment tree. Initialize each node with zero.
- Process Operations: Loop over each operation from 1 to m.
- For each operation:
- If it is of type 1 (update operation):
- Read the left boundary l, right boundary r, and the value to be assigned val.
- Call the update function to update the range [l, r-1] with the value val.
- If it is of type 2 (query operation):
- Read the left boundary l and right boundary r.
- Call the query function to find the minimum value in the range [l, r-1].
- Print the result of the query.
- If it is of type 1 (update operation):
Below is the Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define the maximum size of the array const int MAXN = 1e5 + 5; // Initialize the array, segment tree, and lazy propagation // array int n, q, t[MAXN << 2], lazy[MAXN << 2]; // Function to build the segment tree void build( int v, int tl, int tr) { // If the segment has only one element // Initialize the tree with the array // values if (tl == tr) { t[v] = 0; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2; // Recursively build the left child build(v * 2, tl, tm ); // Recursively build the right child build(v * 2 + 1, tm + 1, tr); // Merge the children values t[v] = min(t[v * 2], t[v * 2 + 1]); } } // Function to propagate the lazy values to the children void push( int v) { // Propagate the value t[v * 2] = t[v * 2 + 1] = lazy[v]; // Update the lazy values for the // children lazy[v * 2] = lazy[v * 2 + 1] = lazy[v]; // Reset the lazy value lazy[v] = 0; } // Function to update a range of the array and the segment // tree void update( int v, int tl, int tr, int l, int r, int val) { // Apply the pending updates if any if (lazy[v]) push(v); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { // Update the tree t[v] = val; // Mark the node for lazy propagation lazy[v] = val; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2; // Recursively update the left child update(v * 2, tl, tm , l, min(r, tm ), val); // Recursively update the right child update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val); // Merge the children values t[v] = min(t[v * 2], t[v * 2 + 1]); } } // Function to query a range of the array int query( int v, int tl, int tr, int l, int r) { // Apply the pending updates if any if (lazy[v]) push(v); // If the range is invalid, return // the maximum possible value if (l > r) return INT_MAX; // If the range matches the segment if (l <= tl && tr <= r) { // Return the value of the segment return t[v]; } // Calculate the middle of the segment int tm = (tl + tr) / 2; // Return the minimum of the // queries on the children return min( query(v * 2, tl, tm , l, min(r, tm )), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)); } int main() { // Number of elements in the array n = 5; // Number of operations q = 6; // Input vector<vector< int > > queries = { { 1, 0, 3, 3 }, { 2, 1, 2 }, { 1, 1, 4, 4 }, { 2, 1, 3 }, { 2, 1, 4 }, { 2, 3, 5 } }; // Build the segment tree build(1, 0, n - 1); // For each operation for ( int i = 0; i < q; i++) { // Type of the operation int type = queries[i][0]; // If the operation is an update if (type == 1) { // Left boundary of the range int l = queries[i][1]; // Right boundary of the range int r = queries[i][2]; // Value to be assigned int val = queries[i][3]; // Update the range update(1, 0, n - 1, l, r - 1, val); } // If the operation is a query else { // Left boundary of the range int l = queries[i][1]; // Right boundary of the range int r = queries[i][2]; // Print the result of the quer cout << query(1, 0, n - 1, l, r - 1) << "\n" ; } } return 0; } |
Java
import java.util.*; public class SegmentTreeLazyPropagation { // Define the maximum size of the array static final int MAXN = 100005 ; // Initialize the array, segment tree, and lazy propagation array static int n, q, t[] = new int [MAXN << 2 ], lazy[] = new int [MAXN << 2 ]; // Function to build the segment tree static void build( int v, int tl, int tr) { // If the segment has only one element, initialize the tree with the array values if (tl == tr) { t[v] = 0 ; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2 ; // Recursively build the left child build(v * 2 , tl, tm); // Recursively build the right child build(v * 2 + 1 , tm + 1 , tr); // Merge the children values t[v] = Math.min(t[v * 2 ], t[v * 2 + 1 ]); } } // Function to propagate the lazy values to the children static void push( int v) { // Propagate the value t[v * 2 ] = t[v * 2 + 1 ] = lazy[v]; // Update the lazy values for the children lazy[v * 2 ] = lazy[v * 2 + 1 ] = lazy[v]; // Reset the lazy value lazy[v] = 0 ; } // Function to update a range of the array and the segment tree static void update( int v, int tl, int tr, int l, int r, int val) { // Apply the pending updates if any if (lazy[v] != 0 ) push(v); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { // Update the tree t[v] = val; // Mark the node for lazy propagation lazy[v] = val; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2 ; // Recursively update the left child update(v * 2 , tl, tm, l, Math.min(r, tm), val); // Recursively update the right child update(v * 2 + 1 , tm + 1 , tr, Math.max(l, tm + 1 ), r, val); // Merge the children values t[v] = Math.min(t[v * 2 ], t[v * 2 + 1 ]); } } // Function to query a range of the array static int query( int v, int tl, int tr, int l, int r) { // Apply the pending updates if any if (lazy[v] != 0 ) push(v); // If the range is invalid, return the maximum possible value if (l > r) return Integer.MAX_VALUE; // If the range matches the segment if (l <= tl && tr <= r) { // Return the value of the segment return t[v]; } // Calculate the middle of the segment int tm = (tl + tr) / 2 ; // Return the minimum of the queries on the children return Math.min(query(v * 2 , tl, tm, l, Math.min(r, tm)), query(v * 2 + 1 , tm + 1 , tr, Math.max(l, tm + 1 ), r)); } public static void main(String[] args) { // Number of elements in the array n = 5 ; // Number of operations q = 6 ; // Input int [][] queries = { { 1 , 0 , 3 , 3 }, { 2 , 1 , 2 }, { 1 , 1 , 4 , 4 }, { 2 , 1 , 3 }, { 2 , 1 , 4 }, { 2 , 3 , 5 } }; // Build the segment tree build( 1 , 0 , n - 1 ); // For each operation for ( int i = 0 ; i < q; i++) { // Type of the operation int type = queries[i][ 0 ]; // If the operation is an update if (type == 1 ) { // Left boundary of the range int l = queries[i][ 1 ]; // Right boundary of the range int r = queries[i][ 2 ]; // Value to be assigned int val = queries[i][ 3 ]; // Update the range update( 1 , 0 , n - 1 , l, r - 1 , val); } // If the operation is a query else { // Left boundary of the range int l = queries[i][ 1 ]; // Right boundary of the range int r = queries[i][ 2 ]; // Print the result of the query System.out.println(query( 1 , 0 , n - 1 , l, r - 1 )); } } } } |
Python3
# Define the maximum size of the array MAXN = 100005 # Initialize the array, segment tree, and lazy propagation array n, q = 0 , 0 t = [ 0 ] * ( 4 * MAXN) lazy = [ 0 ] * ( 4 * MAXN) # Function to build the segment tree def build(v, tl, tr): # If the segment has only one element # Initialize the tree with the array values if tl = = tr: t[v] = 0 else : # Calculate the middle of the segment tm = (tl + tr) / / 2 # Recursively build the left child build(v * 2 , tl, tm) # Recursively build the right child build(v * 2 + 1 , tm + 1 , tr) # Merge the children values t[v] = min (t[v * 2 ], t[v * 2 + 1 ]) # Function to propagate the lazy values to the children def push(v): # Propagate the value t[v * 2 ] = t[v * 2 + 1 ] = lazy[v] # Update the lazy values for the children lazy[v * 2 ] = lazy[v * 2 + 1 ] = lazy[v] # Reset the lazy value lazy[v] = 0 # Function to update a range of the array and the segment tree def update(v, tl, tr, l, r, val): # Apply the pending updates if any if lazy[v]: push(v) # If the range is invalid, return if l > r: return # If the range matches the segment if l = = tl and r = = tr: # Update the tree t[v] = val # Mark the node for lazy propagation lazy[v] = val else : # Calculate the middle of the segment tm = (tl + tr) / / 2 # Recursively update the left child update(v * 2 , tl, tm, l, min (r, tm), val) # Recursively update the right child update(v * 2 + 1 , tm + 1 , tr, max (l, tm + 1 ), r, val) # Merge the children values t[v] = min (t[v * 2 ], t[v * 2 + 1 ]) # Function to query a range of the array def query(v, tl, tr, l, r): # Apply the pending updates if any if lazy[v]: push(v) # If the range is invalid, return the maximum possible value if l > r: return float ( 'inf' ) # If the range matches the segment if l < = tl and tr < = r: # Return the value of the segment return t[v] # Calculate the middle of the segment tm = (tl + tr) / / 2 # Return the minimum of the queries on the children return min (query(v * 2 , tl, tm, l, min (r, tm)), query(v * 2 + 1 , tm + 1 , tr, max (l, tm + 1 ), r)) # Number of elements in the array n = 5 # Number of operations q = 6 # Input queries = [ [ 1 , 0 , 3 , 3 ], [ 2 , 1 , 2 ], [ 1 , 1 , 4 , 4 ], [ 2 , 1 , 3 ], [ 2 , 1 , 4 ], [ 2 , 3 , 5 ] ] # Build the segment tree build( 1 , 0 , n - 1 ) # For each operation for i in range (q): # Type of the operation type = queries[i][ 0 ] # If the operation is an update if type = = 1 : # Left boundary of the range l = queries[i][ 1 ] # Right boundary of the range r = queries[i][ 2 ] # Value to be assigned val = queries[i][ 3 ] # Update the range update( 1 , 0 , n - 1 , l, r - 1 , val) # If the operation is a query else : # Left boundary of the range l = queries[i][ 1 ] # Right boundary of the range r = queries[i][ 2 ] # Print the result of the query print (query( 1 , 0 , n - 1 , l, r - 1 )) |
C#
using System; using System.Collections.Generic; public class GFG { // Define the maximum size of the array const int MAXN = 100005; // Initialize the array, segment tree, and lazy propagation // array static int n, q; static int [] t = new int [MAXN << 2]; static int [] lazy = new int [MAXN << 2]; // Function to build the segment tree static void Build( int v, int tl, int tr) { // If the segment has only one element // Initialize the tree with the array // values if (tl == tr) { t[v] = 0; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2; // Recursively build the left child Build(v * 2, tl, tm); // Recursively build the right child Build(v * 2 + 1, tm + 1, tr); // Merge the children values t[v] = Math.Min(t[v * 2], t[v * 2 + 1]); } } // Function to propagate the lazy values to the children static void Push( int v) { // Propagate the value t[v * 2] = t[v * 2 + 1] = lazy[v]; // Update the lazy values for the // children lazy[v * 2] = lazy[v * 2 + 1] = lazy[v]; // Reset the lazy value lazy[v] = 0; } // Function to update a range of the array and the segment // tree static void Update( int v, int tl, int tr, int l, int r, int val) { // Apply the pending updates if any if (lazy[v] != 0) Push(v); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { // Update the tree t[v] = val; // Mark the node for lazy propagation lazy[v] = val; } else { // Calculate the middle of the segment int tm = (tl + tr) / 2; // Recursively update the left child Update(v * 2, tl, tm, l, Math.Min(r, tm), val); // Recursively update the right child Update(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r, val); // Merge the children values t[v] = Math.Min(t[v * 2], t[v * 2 + 1]); } } // Function to query a range of the array static int Query( int v, int tl, int tr, int l, int r) { // Apply the pending updates if any if (lazy[v] != 0) Push(v); // If the range is invalid, return // the maximum possible value if (l > r) return int .MaxValue; // If the range matches the segment if (l <= tl && tr <= r) { // Return the value of the segment return t[v]; } // Calculate the middle of the segment int tm = (tl + tr) / 2; // Return the minimum of the // queries on the children return Math.Min( Query(v * 2, tl, tm, l, Math.Min(r, tm)), Query(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r)); } public static void Main() { // Number of elements in the array n = 5; // Number of operations q = 6; // Input List<List< int >> queries = new List<List< int >> { new List< int > {1, 0, 3, 3}, new List< int > {2, 1, 2}, new List< int > {1, 1, 4, 4}, new List< int > {2, 1, 3}, new List< int > {2, 1, 4}, new List< int > {2, 3, 5} }; // Build the segment tree Build(1, 0, n - 1); // For each operation for ( int i = 0; i < q; i++) { // Type of the operation int type = queries[i][0]; // If the operation is an update if (type == 1) { // Left boundary of the range int l = queries[i][1]; // Right boundary of the range int r = queries[i][2]; // Value to be assigned int val = queries[i][3]; // Update the range Update(1, 0, n - 1, l, r - 1, val); } // If the operation is a query else { // Left boundary of the range int l = queries[i][1]; // Right boundary of the range int r = queries[i][2]; // Print the result of the query Console.WriteLine(Query(1, 0, n - 1, l, r - 1)); } } } } |
Javascript
// Define the maximum size of the array const MAXN = 100005; // Initialize the array, segment tree, and lazy propagation array let n = 0; let q = 0; let t = new Array(4 * MAXN).fill(0); let lazy = new Array(4 * MAXN).fill(0); // Function to build the segment tree function build(v, tl, tr) { // If the segment has only one element // Initialize the tree with the array values if (tl === tr) { t[v] = 0; } else { // Calculate the middle of the segment const tm = Math.floor((tl + tr) / 2); // Recursively build the left child build(v * 2, tl, tm); // Recursively build the right child build(v * 2 + 1, tm + 1, tr); // Merge the children values t[v] = Math.min(t[v * 2], t[v * 2 + 1]); } } // Function to propagate the lazy values to the children function push(v) { // Propagate the value t[v * 2] = t[v * 2 + 1] = lazy[v]; // Update the lazy values for the children lazy[v * 2] = lazy[v * 2 + 1] = lazy[v]; // Reset the lazy value lazy[v] = 0; } // Function to update a range of the array and the segment tree function update(v, tl, tr, l, r, val) { // Apply the pending updates if any if (lazy[v]) { push(v); } // If the range is invalid, return if (l > r) { return ; } // If the range matches the segment if (l === tl && r === tr) { // Update the tree t[v] = val; // Mark the node for lazy propagation lazy[v] = val; } else { // Calculate the middle of the segment const tm = Math.floor((tl + tr) / 2); // Recursively update the left child update(v * 2, tl, tm, l, Math.min(r, tm), val); // Recursively update the right child update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, val); // Merge the children values t[v] = Math.min(t[v * 2], t[v * 2 + 1]); } } // Function to query a range of the array function query(v, tl, tr, l, r) { // Apply the pending updates if any if (lazy[v]) { push(v); } // If the range is invalid, return the maximum possible value if (l > r) { return Infinity; } // If the range matches the segment if (l <= tl && tr <= r) { // Return the value of the segment return t[v]; } // Calculate the middle of the segment const tm = Math.floor((tl + tr) / 2); // Return the minimum of the queries on the children return Math.min( query(v * 2, tl, tm, l, Math.min(r, tm)), query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r) ); } // Number of elements in the array n = 5; // Number of operations q = 6; // Input const queries = [ [1, 0, 3, 3], [2, 1, 2], [1, 1, 4, 4], [2, 1, 3], [2, 1, 4], [2, 3, 5] ]; // Build the segment tree build(1, 0, n - 1); // For each operation for (let i = 0; i < q; i++) { // Type of the operation const type = queries[i][0]; // If the operation is an update if (type === 1) { // Left boundary of the range const l = queries[i][1]; // Right boundary of the range const r = queries[i][2]; // Value to be assigned const val = queries[i][3]; // Update the range update(1, 0, n - 1, l, r - 1, val); } else { // If the operation is a query // Left boundary of the range const l = queries[i][1]; // Right boundary of the range const r = queries[i][2]; // Print the result of the query console.log(query(1, 0, n - 1, l, r - 1)); } } |
3 4 4 0
Time Complexity:
- Build Function: O(n)
- Update Function: O(log n)
- Query Function: O(log n)
- Overall: O(n + m log n)
Auxiliary Space: O(n) for segment