Horje
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
0

Input: 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

Output

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)

 


Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Longest strictly decreasing subsequence such that no two adjacent elements are coprime Longest strictly decreasing subsequence such that no two adjacent elements are coprime
3D Kadane&#039;s Algorithm 3D Kadane&#039;s Algorithm
Minimize operations to restore original string by permutation Minimize operations to restore original string by permutation
Optimization for Unordered Map O(1) operations Optimization for Unordered Map O(1) operations
GeeksforGeeks Problem Of The Day (POTD) Solutions | December 2023 GeeksforGeeks Problem Of The Day (POTD) Solutions | December 2023

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



 

Horje