6

Range Minimum Query with Range Assignment

 1 year ago
source link: https://www.geeksforgeeks.org/range-minimum-query-with-range-assignment/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Range Minimum Query with Range Assignment

Courses
Practice

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:

#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;
}
Output 
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

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 geeks!

Commit to GfG's Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.
Recommended Problems
Frequently asked DSA Problems
Last Updated : 10 Jan, 2024
Like Article
Save Article
Share your thoughts in the comments

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK