Segment Tree for Range Addition and Range Minimum Query
Given an array of size N initially filled with 0s. There are Q queries to be performed, and each query can be one of two types:
- Type 1 (1, L, R, X): Add X to all elements in the segment from L to R−1.
- Type 2 (2, L, R): Find the minimum value in the segment from L to R−1.
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
7
4
0
Approach:
The idea is to use Segment Tree with Lazy Propagation. It’s used to efficiently perform range update and range query operations on an array.
- The build function constructs the segment tree from the input array.
- The update function updates a range of values in the array and marks nodes for lazy updates.
- The query function finds the minimum value in a range, taking into account any pending lazy updates.
Steps-by-step approach:
- Define constants for the maximum size of the array and the segment tree.
- Create a function to build the segment tree recursively.
- Create a function to update a range in the array with lazy propagation.
- Create a function to query a range in the array with lazy propagation.
- In the main function:
- Build the initial segment tree with zeros.
- Define queries as a vector of vectors.
- For each query:
- If it’s a type 1 query, update the array using lazy propagation.
- If it’s a type 2 query, query the array and print the result.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h> using namespace std; const int MAX = 1e5; // Max size of array int tree[4*MAX]; // Segment tree int lazy[4*MAX]; // Lazy array to propagate updates // Function to build the tree void build( int node, int start, int end) { if (start == end) { // Leaf node will have a single element tree[node] = 0; } else { int mid = (start + end) / 2; // Recur for the 2 children build(2*node, start, mid); build(2*node+1, mid+1, end); // Internal node will have the minimum of both of its children tree[node] = min(tree[2*node], tree[2*node+1]); } } // Function to update a node void update( int node, int start, int end, int l, int r, int val) { if (lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start > end or start > r or end < l) return ; // Current segment is not within range [l, r] if (start >= l and end <= r) { // Segment is fully within range tree[node] += val; if (start != end) { // Not leaf node lazy[node*2] += val; lazy[node*2+1] += val; } return ; } int mid = (start + end) / 2; update(node*2, start, mid, l, r, val); // Updating left child update(node*2 + 1, mid + 1, end, l, r, val); // Updating right child tree[node] = min(tree[node*2], tree[node*2+1]); // Updating root with min value } // Function to query the tree int query( int node, int start, int end, int l, int r) { if (start > end or start > r or end < l) return MAX; // Out of range if (lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start >= l and end <= r) // Current segment is totally within range [l, r] return tree[node]; int mid = (start + end) / 2; int p1 = query(node*2, start, mid, l, r); // Query left child int p2 = query(node*2 + 1, mid + 1, end, l, r); // Query right child return min(p1, p2); } int main() { int n = 5; build(1, 0, n-1); // Define the queries vector<vector< int >> queries = { {1, 0, 3, 3}, {2, 1, 2}, {1, 1, 4, 4}, {2, 1, 3}, {2, 1, 4}, {2, 3, 5} }; for ( auto &q : queries) { int type = q[0]; if (type == 1) { int l = q[1], r = q[2], x = q[3]; update(1, 0, n-1, l, r-1, x); // Update the array } else if (type == 2) { int l = q[1], r = q[2]; int ans = query(1, 0, n-1, l, r-1); // Query the array cout << ans << endl; } } return 0; } |
Java
import java.util.*; public class SegmentTree { static final int MAX = 100000 ; // Max size of array static int [] tree = new int [ 4 * MAX]; // Segment tree static int [] lazy = new int [ 4 * MAX]; // Lazy array to propagate updates // Function to build the tree static void build( int node, int start, int end) { if (start == end) { // Leaf node will have a single element tree[node] = 0 ; } else { int mid = (start + end) / 2 ; // Recur for the 2 children build( 2 * node, start, mid); build( 2 * node + 1 , mid + 1 , end); // Internal node will have the minimum of both of its children tree[node] = Math.min(tree[ 2 * node], tree[ 2 * node + 1 ]); } } // Function to update a node static void update( int node, int start, int end, int l, int r, int val) { if (lazy[node] != 0 ) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node * 2 ] += lazy[node]; // Mark left child as lazy lazy[node * 2 + 1 ] += lazy[node]; // Mark right child as lazy } lazy[node] = 0 ; // Reset it } if (start > end || start > r || end < l) return ; // Current segment is not within range [l, r] if (start >= l && end <= r) { // Segment is fully within range tree[node] += val; if (start != end) { // Not leaf node lazy[node * 2 ] += val; lazy[node * 2 + 1 ] += val; } return ; } int mid = (start + end) / 2 ; update(node * 2 , start, mid, l, r, val); // Updating left child update(node * 2 + 1 , mid + 1 , end, l, r, val); // Updating right child tree[node] = Math.min(tree[node * 2 ], tree[node * 2 + 1 ]); // Updating root with min value } // Function to query the tree static int query( int node, int start, int end, int l, int r) { if (start > end || start > r || end < l) return MAX; // Out of range if (lazy[node] != 0 ) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node * 2 ] += lazy[node]; // Mark left child as lazy lazy[node * 2 + 1 ] += lazy[node]; // Mark right child as lazy } lazy[node] = 0 ; // Reset it } if (start >= l && end <= r) return tree[node]; // Current segment is totally within range [l, r] int mid = (start + end) / 2 ; int p1 = query(node * 2 , start, mid, l, r); // Query left child int p2 = query(node * 2 + 1 , mid + 1 , end, l, r); // Query right child return Math.min(p1, p2); } public static void main(String[] args) { int n = 5 ; build( 1 , 0 , n - 1 ); // Define the queries List< int []> queries = Arrays.asList( new int []{ 1 , 0 , 3 , 3 }, new int []{ 2 , 1 , 2 }, new int []{ 1 , 1 , 4 , 4 }, new int []{ 2 , 1 , 3 }, new int []{ 2 , 1 , 4 }, new int []{ 2 , 3 , 5 } ); for ( int [] q : queries) { int type = q[ 0 ]; if (type == 1 ) { int l = q[ 1 ], r = q[ 2 ], x = q[ 3 ]; update( 1 , 0 , n - 1 , l, r - 1 , x); // Update the array } else if (type == 2 ) { int l = q[ 1 ], r = q[ 2 ]; int ans = query( 1 , 0 , n - 1 , l, r - 1 ); // Query the array System.out.println(ans); } } } } |
C#
using System; using System.Collections.Generic; class SegmentTree { const int MAX = 100000; // Max size of array int [] tree = new int [4 * MAX]; // Segment tree int [] lazy = new int [4 * MAX]; // Lazy array to propagate updates // Function to build the tree void Build( int node, int start, int end) { if (start == end) { // Leaf node will have a single element tree[node] = 0; } else { int mid = (start + end) / 2; // Recur for the 2 children Build(2 * node, start, mid); Build(2 * node + 1, mid + 1, end); // Internal node will have the minimum of both of its children tree[node] = Math.Min(tree[2 * node], tree[2 * node + 1]); } } // Function to update a node void Update( int node, int start, int end, int l, int r, int val) { if (lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node * 2] += lazy[node]; // Mark child as lazy lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start > end || start > r || end < l) return ; // Current segment is not within range [l, r] if (start >= l && end <= r) { // Segment is fully within range tree[node] += val; if (start != end) { // Not a leaf node lazy[node * 2] += val; lazy[node * 2 + 1] += val; } return ; } int mid = (start + end) / 2; Update(node * 2, start, mid, l, r, val); // Updating left child Update(node * 2 + 1, mid + 1, end, l, r, val); // Updating right child tree[node] = Math.Min(tree[node * 2], tree[node * 2 + 1]); // Updating root with min value } // Function to query the tree int Query( int node, int start, int end, int l, int r) { if (start > end || start > r || end < l) return int .MaxValue; // Out of range if (lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start != end) { lazy[node * 2] += lazy[node]; // Mark child as lazy lazy[node * 2 + 1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start >= l && end <= r) // Current segment is totally within range [l, r] return tree[node]; int mid = (start + end) / 2; int p1 = Query(node * 2, start, mid, l, r); // Query left child int p2 = Query(node * 2 + 1, mid + 1, end, l, r); // Query right child return Math.Min(p1, p2); } static void Main() { int n = 5; var segmentTree = new SegmentTree(); segmentTree.Build(1, 0, n - 1); // Define the queries var queries = new List< int []>() { new int [] {1, 0, 3, 3}, new int [] {2, 1, 2}, new int [] {1, 1, 4, 4}, new int [] {2, 1, 3}, new int [] {2, 1, 4}, new int [] {2, 3, 5} }; foreach ( var q in queries) { int type = q[0]; if (type == 1) { int l = q[1], r = q[2], x = q[3]; segmentTree.Update(1, 0, n - 1, l, r - 1, x); // Update the array } else if (type == 2) { int l = q[1], r = q[2]; int ans = segmentTree.Query(1, 0, n - 1, l, r - 1); // Query the array Console.WriteLine(ans); } } } } |
Javascript
const MAX = 1e5; // Max size of array let tree = new Array(4*MAX).fill(0); // Segment tree let lazy = new Array(4*MAX).fill(0); // Lazy array to propagate updates // Function to build the tree function build(node, start, end) { if (start === end) { // Leaf node will have a single element tree[node] = 0; } else { let mid = Math.floor((start + end) / 2); // Recur for the 2 children build(2*node, start, mid); build(2*node+1, mid+1, end); // Internal node will have the minimum of both of its children tree[node] = Math.min(tree[2*node], tree[2*node+1]); } } // Function to update a node function update(node, start, end, l, r, val) { if (lazy[node] !== 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start !== end) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start > end || start > r || end < l) return ; // Current segment is not within range [l, r] if (start >= l && end <= r) { // Segment is fully within range tree[node] += val; if (start !== end) { // Not leaf node lazy[node*2] += val; lazy[node*2+1] += val; } return ; } let mid = Math.floor((start + end) / 2); update(node*2, start, mid, l, r, val); // Updating left child update(node*2 + 1, mid + 1, end, l, r, val); // Updating right child tree[node] = Math.min(tree[node*2], tree[node*2+1]); // Updating root with min value } // Function to query the tree function query(node, start, end, l, r) { if (start > end || start > r || end < l) return MAX; // Out of range if (lazy[node] !== 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if (start !== end) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if (start >= l && end <= r) // Current segment is totally within range [l, r] return tree[node]; let mid = Math.floor((start + end) / 2); let p1 = query(node*2, start, mid, l, r); // Query left child let p2 = query(node*2 + 1, mid + 1, end, l, r); // Query right child return Math.min(p1, p2); } // Main function function main() { let n = 5; build(1, 0, n-1); // Define the queries let queries = [ [1, 0, 3, 3], [2, 1, 2], [1, 1, 4, 4], [2, 1, 3], [2, 1, 4], [2, 3, 5] ]; for (let q of queries) { let type = q[0]; if (type === 1) { let l = q[1], r = q[2], x = q[3]; update(1, 0, n-1, l, r-1, x); // Update the array } else if (type === 2) { let l = q[1], r = q[2]; let ans = query(1, 0, n-1, l, r-1); // Query the array console.log(ans); } } } main(); |
Python3
MAX = int ( 1e5 ) # Max size of array tree = [ 0 ] * ( 4 * MAX ) # Segment tree lazy = [ 0 ] * ( 4 * MAX ) # Lazy array to propagate updates # Function to build the tree def build(node, start, end): if start = = end: # Leaf node will have a single element tree[node] = 0 else : mid = (start + end) / / 2 # Recur for the 2 children build( 2 * node, start, mid) build( 2 * node + 1 , mid + 1 , end) # Internal node will have the minimum of both of its children tree[node] = min (tree[ 2 * node], tree[ 2 * node + 1 ]) # Function to update a node def update(node, start, end, l, r, val): if lazy[node] ! = 0 : # This node needs to be updated tree[node] + = lazy[node] # Update it if start ! = end: lazy[node * 2 ] + = lazy[node] # Mark child as lazy lazy[node * 2 + 1 ] + = lazy[node] # Mark child as lazy lazy[node] = 0 # Reset it if start > end or start > r or end < l: return # Current segment is not within range [l, r] if start > = l and end < = r: # Segment is fully within range tree[node] + = val if start ! = end: # Not leaf node lazy[node * 2 ] + = val lazy[node * 2 + 1 ] + = val return mid = (start + end) / / 2 update(node * 2 , start, mid, l, r, val) # Updating left child update(node * 2 + 1 , mid + 1 , end, l, r, val) # Updating right child tree[node] = min (tree[node * 2 ], tree[node * 2 + 1 ]) # Updating root with min value # Function to query the tree def query(node, start, end, l, r): if start > end or start > r or end < l: return MAX # Out of range if lazy[node] ! = 0 : # This node needs to be updated tree[node] + = lazy[node] # Update it if start ! = end: lazy[node * 2 ] + = lazy[node] # Mark child as lazy lazy[node * 2 + 1 ] + = lazy[node] # Mark child as lazy lazy[node] = 0 # Reset it if start > = l and end < = r: # Current segment is totally within range [l, r] return tree[node] mid = (start + end) / / 2 p1 = query(node * 2 , start, mid, l, r) # Query left child p2 = query(node * 2 + 1 , mid + 1 , end, l, r) # Query right child return min (p1, p2) # Main function def main(): n = 5 build( 1 , 0 , n - 1 ) # Define the queries queries = [ [ 1 , 0 , 3 , 3 ], [ 2 , 1 , 2 ], [ 1 , 1 , 4 , 4 ], [ 2 , 1 , 3 ], [ 2 , 1 , 4 ], [ 2 , 3 , 5 ] ] for q in queries: type = q[ 0 ] if type = = 1 : l, r, x = q[ 1 ], q[ 2 ], q[ 3 ] update( 1 , 0 , n - 1 , l, r - 1 , x) # Update the array elif type = = 2 : l, r = q[ 1 ], q[ 2 ] ans = query( 1 , 0 , n - 1 , l, r - 1 ) # Query the array print (ans) main() |
Output
3 7 4 0
Time Complexity: O(log n) per query and update, O(n) for the construction of the segment tree.
Auxiliary Space : O(n) for the segment tree.
Contact Us