Segment Tree for Range Bitwise OR and Range Minimum Queries
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 queries in the format {1, l, r, v} and type 2 queries in the format {2, l, r}.
- Type 1: Apply the operation ai = ai | v (bitwise OR) to all elements on the segment l to r.
- Type 2: Find the minimum on the segment from l to r.
Examples:
Input: n = 5, q = 6, queries[6][4] = {{1, 0, 3, 3}, {2, 1, 2}, {1, 1, 4, 4}, {2, 1, 3}, {2, 1, 4}, {2, 3, 5} };
Output:
3
7
4
0Input: n = 2, q = 3, queries[3][4] = {{1, 0, 1, 3}, {1, 1, 2, 9}, {2, 0, 2}};
Output: 1
Approach: To solve the problem follow the below idea
The solution uses a segment tree data structure. We’ll also uses lazy propagation to optimize the update operation. Lazy propagation is a strategy where, instead of updating the segment tree immediately after a query of type 1, the update is postponed and stored in a separate array called lazy. The lazy array keeps track of the pending updates for each node of the segment tree. The pending updates are applied only when they are needed, i.e., when a query of type 2 is performed on a node or its descendants.
Steps were taken to implement the idea:
Initialization:
- Define constants for the maximum size of the array (MAXN) and the maximum number of bits (MAXV).
- Declare variables for the array size (n), the number of operations (m), the array (a), and the segment tree (t).
Build Segment Tree:
- Create a function build to initialize the segment tree.
- If the segment has only one element, set the tree values based on the corresponding bits in the array.
- Otherwise, recursively build the left and right children, merging their values.
Lazy Propagation:
- Create a function push to propagate lazy values to the children of a segment.
- If the segment has more than one element, update the children based on the lazy values.
Update Operation:
- Create a function update to apply an update operation to a range of the array and the segment tree.
- Propagate lazy values, handle invalid ranges, and update the tree and lazy values based on the given range and value.
Query Operation:
- Create a function query to find the bitwise AND of elements in a range of the array.
- Propagate lazy values, handle invalid ranges, and return the bitwise AND of the segment.
Main Function:
- Read input for array size and the number of operations.
- Build the initial segment tree using the build function.
- Iterate through each operation:
- If it’s an update operation, apply the update using the update function.
- If it’s a query operation, print the result of the query using the query function.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define the maximum size of the array and the maximum // value const int MAXN = 1e5 + 5; const int MAXV = 30; // Initialize the array, segment tree, and lazy propagation // array int n, m, a[MAXN], t[MAXN << 2][MAXV], lazy[MAXN << 2][MAXV]; // Function to build the segment tree void build( int v, int tl, int tr) { // If the segment has only one element if (tl == tr) { // Initialize the tree with the // array values for ( int i = 0; i < MAXV; i++) { t[v][i] = ((a[tl] >> i) & 1); } } 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 for ( int i = 0; i < MAXV; i++) { t[v][i] = t[v * 2][i] & t[v * 2 + 1][i]; } } } // Function to propagate the lazy values to the children void push( int v, int tl, int tr) { // If the segment has more than one element if (tl != tr) { for ( int i = 0; i < MAXV; i++) { // If there is a value to // propagate if (lazy[v][i]) { // Propagate the value t[v * 2][i] = t[v * 2 + 1][i] = lazy[v * 2][i] = lazy[v * 2 + 1][i] = 1; // Reset the lazy value lazy[v][i] = 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) { // Propagate the lazy values before the update push(v, tl, tr); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { for ( int i = 0; i < MAXV; i++) { // If the value affects this bit if ((val >> i) & 1) { // Update the tree and the lazy // values t[v][i] = lazy[v][i] = 1; } } } 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); for ( int i = 0; i < MAXV; i++) { // Merge the children values t[v][i] = t[v * 2][i] & t[v * 2 + 1][i]; } } } // Function to query a range of the array int query( int v, int tl, int tr, int l, int r) { // Propagate the lazy values before the query push(v, tl, tr); // If the range is invalid, return the // maximum possible value if (l > r) return (1 << MAXV) - 1; // If the range matches the segment if (l <= tl && tr <= r) { int res = 0; for ( int i = 0; i < MAXV; i++) { // If this bit is set if (t[v][i]) { // Add it to the result res |= (1 << i); } } return res; } // Calculate the middle of the segment int tm = (tl + tr) / 2; // Return the AND of the queries on // the children return query(v * 2, tl, tm , l, min(r, tm )) & query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r); } int main() { n = 2; m = 3; int operations[3][4] = { { 1, 0, 1, 3 }, { 1, 1, 2, 9 }, { 2, 0, 2 } }; build(1, 0, n - 1); for ( int i = 0; i < m; i++) { int type = operations[i][0]; if (type == 1) { int l = operations[i][1]; int r = operations[i][2]; int val = operations[i][3]; update(1, 0, n - 1, l, r - 1, val); } else { int l = operations[i][1]; int r = operations[i][2]; 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 and the maximum value static final int MAXN = 100005 ; static final int MAXV = 30 ; // Initialize the array, segment tree, and lazy propagation array static int n, m; static int [] a = new int [MAXN]; static int [][] t = new int [MAXN << 2 ][MAXV]; static int [][] lazy = new int [MAXN << 2 ][MAXV]; // Function to build the segment tree static void build( int v, int tl, int tr) { // If the segment has only one element if (tl == tr) { // Initialize the tree with the array values for ( int i = 0 ; i < MAXV; i++) { t[v][i] = ((a[tl] >> i) & 1 ); } } 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 for ( int i = 0 ; i < MAXV; i++) { t[v][i] = t[v * 2 ][i] & t[v * 2 + 1 ][i]; } } } // Function to propagate the lazy values to the children static void push( int v, int tl, int tr) { // If the segment has more than one element if (tl != tr) { for ( int i = 0 ; i < MAXV; i++) { // If there is a value to propagate if (lazy[v][i] != 0 ) { // Propagate the value t[v * 2 ][i] = t[v * 2 + 1 ][i] = lazy[v * 2 ][i] = lazy[v * 2 + 1 ][i] = 1 ; // Reset the lazy value lazy[v][i] = 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) { // Propagate the lazy values before the update push(v, tl, tr); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { for ( int i = 0 ; i < MAXV; i++) { // If the value affects this bit if (((val >> i) & 1 ) == 1 ) { // Update the tree and the lazy values t[v][i] = lazy[v][i] = 1 ; } } } 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); for ( int i = 0 ; i < MAXV; i++) { // Merge the children values t[v][i] = t[v * 2 ][i] & t[v * 2 + 1 ][i]; } } } // Function to query a range of the array static int query( int v, int tl, int tr, int l, int r) { // Propagate the lazy values before the query push(v, tl, tr); // If the range is invalid, return the maximum possible value if (l > r) return ( 1 << MAXV) - 1 ; // If the range matches the segment if (l <= tl && tr <= r) { int res = 0 ; for ( int i = 0 ; i < MAXV; i++) { // If this bit is set if (t[v][i] == 1 ) { // Add it to the result res |= ( 1 << i); } } return res; } // Calculate the middle of the segment int tm = (tl + tr) / 2 ; // Return the AND of the queries on the children return 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) { n = 2 ; m = 3 ; int [][] operations = { { 1 , 0 , 1 , 3 }, { 1 , 1 , 2 , 9 }, { 2 , 0 , 2 } }; build( 1 , 0 , n - 1 ); for ( int i = 0 ; i < m; i++) { int type = operations[i][ 0 ]; if (type == 1 ) { int l = operations[i][ 1 ]; int r = operations[i][ 2 ]; int val = operations[i][ 3 ]; update( 1 , 0 , n - 1 , l, r - 1 , val); } else { int l = operations[i][ 1 ]; int r = operations[i][ 2 ]; System.out.println(query( 1 , 0 , n - 1 , l, r - 1 )); } } } } |
C#
using System; public class MainClass { // Define the maximum size of the array and the maximum value const int MAXN = 100005; const int MAXV = 30; // Initialize the array, segment tree, and lazy propagation array static int n, m; static int [,] a = new int [MAXN, MAXV]; static int [,] t = new int [MAXN << 2, MAXV]; static int [] lazy = new int [MAXN << 2]; // Change from 2D to 1D array for lazy propagation // Function to build the segment tree static void Build( int v, int tl, int tr) { // If the segment has only one element if (tl == tr) { // Initialize the tree with the array values for ( int i = 0; i < MAXV; i++) { t[v, i] = ((a[tl, i] >> i) & 1); } } 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 for ( int i = 0; i < MAXV; i++) { t[v, i] = t[v * 2, i] & t[v * 2 + 1, i]; } } } // Function to propagate the lazy values to the children static void Push( int v, int tl, int tr) { // If the segment has more than one element if (tl != tr) { for ( int i = 0; i < MAXV; i++) { // If there is a value to propagate if (lazy[v] != 0) { // Propagate the value t[v * 2, i] = t[v * 2 + 1, i] = lazy[v * 2] = lazy[v * 2 + 1] = 1; // 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) { // Propagate the lazy values before the update Push(v, tl, tr); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l == tl && r == tr) { for ( int i = 0; i < MAXV; i++) { // If the value affects this bit if (((val >> i) & 1) != 0) { // Update the tree and the lazy values t[v, i] = lazy[v] = 1; } } } 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); for ( int i = 0; i < MAXV; i++) { // Merge the children values t[v, i] = t[v * 2, i] & t[v * 2 + 1, i]; } } } // Function to query a range of the array static int Query( int v, int tl, int tr, int l, int r) { // Propagate the lazy values before the query Push(v, tl, tr); // If the range is invalid, return the maximum possible value if (l > r) return (1 << MAXV) - 1; // If the range matches the segment if (l <= tl && tr <= r) { int res = 0; for ( int i = 0; i < MAXV; i++) { // If this bit is set if (t[v, i] != 0) { // Add it to the result res |= (1 << i); } } return res; } // Calculate the middle of the segment int tm = (tl + tr) / 2; // Return the AND of the queries on the children return 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) { n = 2; m = 3; int [,] operations = new int [3, 4] { { 1, 0, 1, 3 }, { 1, 1, 2, 9 }, { 2, 0, 2, 0 } }; Build(1, 0, n - 1); for ( int i = 0; i < m; i++) { int type = operations[i, 0]; if (type == 1) { int l = operations[i, 1]; int r = operations[i, 2]; int val = operations[i, 3]; Update(1, 0, n - 1, l, r - 1, val); } else { int l = operations[i, 1]; int r = operations[i, 2]; Console.WriteLine(Query(1, 0, n - 1, l, r - 1)); } } } } |
Javascript
// Define the maximum size of the array and the maximum value const MAXN = 100005; const MAXV = 30; // Initialize the array, segment tree, and lazy propagation array let n = 2, m = 3; let a = Array(MAXN).fill(0); let t = Array.from(Array(MAXN << 2), () => Array(MAXV).fill(0)); let lazy = Array.from(Array(MAXN << 2), () => Array(MAXV).fill(0)); // Function to build the segment tree function build(v, tl, tr) { // If the segment has only one element if (tl === tr) { // Initialize the tree with the array values for (let i = 0; i < MAXV; i++) { t[v][i] = ((a[tl] >> i) & 1); } } else { // Calculate the middle of the segment let 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 for (let i = 0; i < MAXV; i++) { t[v][i] = t[v * 2][i] & t[v * 2 + 1][i]; } } } // Function to propagate the lazy values to the children function push(v, tl, tr) { // If the segment has more than one element if (tl !== tr) { for (let i = 0; i < MAXV; i++) { // If there is a value to propagate if (lazy[v][i]) { // Propagate the value t[v * 2][i] = t[v * 2 + 1][i] = lazy[v * 2][i] = lazy[v * 2 + 1][i] = 1; // Reset the lazy value lazy[v][i] = 0; } } } } // Function to update a range of the array and the segment tree function update(v, tl, tr, l, r, val) { // Propagate the lazy values before the update push(v, tl, tr); // If the range is invalid, return if (l > r) return ; // If the range matches the segment if (l === tl && r === tr) { for (let i = 0; i < MAXV; i++) { // If the value affects this bit if ((val >> i) & 1) { // Update the tree and the lazy values t[v][i] = lazy[v][i] = 1; } } } else { // Calculate the middle of the segment let 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); for (let i = 0; i < MAXV; i++) { // Merge the children values t[v][i] = t[v * 2][i] & t[v * 2 + 1][i]; } } } // Function to query a range of the array function query(v, tl, tr, l, r) { // Propagate the lazy values before the query push(v, tl, tr); // If the range is invalid, return the maximum possible value if (l > r) return (1 << MAXV) - 1; // If the range matches the segment if (l <= tl && tr <= r) { let res = 0; for (let i = 0; i < MAXV; i++) { // If this bit is set if (t[v][i]) { // Add it to the result res |= (1 << i); } } return res; } // Calculate the middle of the segment let tm = Math.floor((tl + tr) / 2); // Return the AND of the queries on the children return query(v * 2, tl, tm, l, Math.min(r, tm)) & query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r); } function main() { // Define the operations to be performed let operations = [[1, 0, 1, 3], [1, 1, 2, 9], [2, 0, 2]]; // Build the segment tree build(1, 0, n - 1); for (let i = 0; i < m; i++) { let type = operations[i][0]; // If the operation is an update if (type === 1) { let l = operations[i][1]; let r = operations[i][2]; let val = operations[i][3]; // Update the array and the segment tree update(1, 0, n - 1, l, r - 1, val); } else { // If the operation is a query let l = operations[i][1]; let r = operations[i][2]; // Query the array and print the result console.log(query(1, 0, n - 1, l, r - 1)); } } } main(); |
Python3
class SegmentTree: def __init__( self , n): # Define the maximum size of the array and the maximum value self .n = n self .MAXV = 30 # Initialize the array, segment tree, and lazy propagation array self .t = [[ 0 ] * self .MAXV for _ in range (n * 4 )] self .lazy = [[ 0 ] * self .MAXV for _ in range (n * 4 )] def build( self , v, tl, tr, a): # If the segment has only one element if tl = = tr: # Initialize the tree with the array values for i in range ( self .MAXV): self .t[v][i] = ((a[tl] >> i) & 1 ) else : # Calculate the middle of the segment tm = (tl + tr) / / 2 # Recursively build the left child self .build(v * 2 , tl, tm, a) # Recursively build the right child self .build(v * 2 + 1 , tm + 1 , tr, a) # Merge the children values for i in range ( self .MAXV): self .t[v][i] = self .t[v * 2 ][i] & self .t[v * 2 + 1 ][i] def push( self , v, tl, tr): # If the segment has more than one element if tl ! = tr: for i in range ( self .MAXV): # If there is a value to propagate if self .lazy[v][i]: # Propagate the value self .t[v * 2 ][i] = self .t[v * 2 + 1 ][i] = self .lazy[v * 2 ][i] = self .lazy[v * 2 + 1 ][i] = 1 # Reset the lazy value self .lazy[v][i] = 0 def update( self , v, tl, tr, l, r, val): # Propagate the lazy values before the update self .push(v, tl, tr) # If the range is invalid, return if l > r: return # If the range matches the segment if l = = tl and r = = tr: for i in range ( self .MAXV): # If the value affects this bit if (val >> i) & 1 : # Update the tree and the lazy values self .t[v][i] = self .lazy[v][i] = 1 else : # Calculate the middle of the segment tm = (tl + tr) / / 2 # Recursively update the left child self .update(v * 2 , tl, tm, l, min (r, tm), val) # Recursively update the right child self .update(v * 2 + 1 , tm + 1 , tr, max (l, tm + 1 ), r, val) for i in range ( self .MAXV): # Merge the children values self .t[v][i] = self .t[v * 2 ][i] & self .t[v * 2 + 1 ][i] def query( self , v, tl, tr, l, r): # Propagate the lazy values before the query self .push(v, tl, tr) # If the range is invalid, return the maximum possible value if l > r: return ( 1 << self .MAXV) - 1 # If the range matches the segment if l < = tl and tr < = r: res = 0 for i in range ( self .MAXV): # If this bit is set if self .t[v][i]: # Add it to the result res | = ( 1 << i) return res # Calculate the middle of the segment tm = (tl + tr) / / 2 # Return the AND of the queries on the children return self .query(v * 2 , tl, tm, l, min (r, tm)) & self .query(v * 2 + 1 , tm + 1 , tr, max (l, tm + 1 ), r) n = 2 m = 3 a = [ 0 , 0 ] # Define operations: [type, l, r, val] operations = [[ 1 , 0 , 1 , 3 ], [ 1 , 1 , 2 , 9 ], [ 2 , 0 , 2 ]] # Initialize and build the segment tree segment_tree = SegmentTree(n) segment_tree.build( 1 , 0 , n - 1 , a) # Process each operation for operation in operations: type_op = operation[ 0 ] if type_op = = 1 : l, r, val = operation[ 1 ], operation[ 2 ], operation[ 3 ] # Update operation segment_tree.update( 1 , 0 , n - 1 , l, r - 1 , val) else : l, r = operation[ 1 ], operation[ 2 ] # Query operation print (segment_tree.query( 1 , 0 , n - 1 , l, r - 1 )) # This code is contributed by akshitaguprzj3 |
1
Time Complexity: O((n + m) * log(n) * MAXV)
- Build Operation: O(n * MAXV * log(n))
- Update Operation: O(log(n) * MAXV)
- Query Operation: O(log(n) * MAXV)
- Overall: O((n + m) * log(n) * MAXV)
Auxiliary Space: O(n * MAXV)
- Segment Tree: O(n * MAXV)
- Lazy Propagation Array: O(n * MAXV)
- Other Variables: O(1)
Contact Us