Range Minimum Query with Range Assignment - Coding

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.

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));
    }
}

Output

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

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Suffix Product Array
Minimize Acceleration of Car to Cover Track
Contest Experience : Leetcode Weekly Contest #375
Minimize replacements to sort an array with elements 1, 2, and 3
Constructing Palindromic Arrays with First Element as X

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	16