Use cases of Lazy Propagation in Competitive Programming
1. Applying MAX to Segment:
Given an array of n elements, initialized with zero. The task is two process two types of queries:
- for all i from l to r do the operation ai = max(ai, val),
- find the current value of element i.
The idea is to apply the update operation in such a way that operations are deeper in the tree than the newer ones so that when we have a get operation, we can simply go from leaf to root, and newer operations will be encountered after the older operations.
To implement this we make a lazy update. A visited node will mean, that every element of the corresponding segment is assigned the operation with value equal to the value of that node. Suppose we have to apply max operation to whole array with value val, the value is placed at the root of the tree. Now suppose the second operation says apply max to first part of the array. To solve this, we first visit the root vertex, since it has been already visited and assigned an operation, we assign that operation to its left and right child and then apply the current operation to left child again. In this way no Information is lost and also the older operations will be stored at a deeper level. The time complexity of both get and update operation will be O(log n).
Below is the implementation of above approach:
typedef long long ll;
void spread(vector<ll>& b, vector<ll>& vis, ll v)
{
if (vis[v]) {
b[v * 2] = max(b[v], b[v * 2]);
b[v * 2 + 1] = max(b[v], b[v * 2 + 1]);
vis[v * 2] = 1;
vis[v * 2 + 1] = 1;
vis[v] = 0;
}
}
void update(vector<ll>& b, vector<ll>& vis, ll v, ll tl,
ll tr, ll l, ll r, ll val)
{
if (l > r)
return;
if (l == tl && r == tr) {
b[v] = max(val, b[v]);
vis[v] = 1;
return;
}
spread(b, vis, v);
ll tm = (tl + tr) / 2;
update(b, vis, v * 2, tl, tm, l, min(r, tm), val);
update(b, vis, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r,
val);
}
ll get(vector<ll>& b, ll v, ll tl, ll tr, ll pos)
{
if (tl == tr)
return b[v];
ll tm = (tl + tr) / 2;
if (pos <= tm)
return max(get(b, v * 2, tl, tm, pos), b[v]);
else
return max(get(b, v * 2 + 1, tm + 1, tr, pos),
b[v]);
}
import java.util.*;
public class Main {
// Defining the function 'spread'
public static void spread(int[] b, int[] vis, int v)
{
// If 'v' is visited
if (vis[v] == 1) {
// Updating the values in the array 'b'
b[v * 2] = Math.max(b[v], b[v * 2]);
b[v * 2 + 1] = Math.max(b[v], b[v * 2 + 1]);
// Marking the elements as visited
vis[v * 2] = 1;
vis[v * 2 + 1] = 1;
vis[v] = 0;
}
}
// Defining the function 'update'
public static void update(int[] b, int[] vis, int v,
int tl, int tr, int l, int r,
int val)
{
// If 'l' is greater than 'r', then return
if (l > r) {
return;
}
// If 'l' is equal to 'tl' and 'r' is equal to 'tr'
if (l == tl && r == tr) {
// Updating the value in the array 'b'
b[v] = Math.max(val, b[v]);
// Marking the element as visited
vis[v] = 1;
return;
}
// Calling the function 'spread'
spread(b, vis, v);
int tm = (tl + tr) / 2;
// Recursive calls to the function 'update'
update(b, vis, v * 2, tl, tm, l, Math.min(r, tm),
val);
update(b, vis, v * 2 + 1, tm + 1, tr,
Math.max(l, tm + 1), r, val);
}
// Defining the function 'get'
public static int get(int[] b, int v, int tl, int tr,
int pos)
{
// If 'tl' is equal to 'tr', then return the value
// at index 'v' in the array 'b'
if (tl == tr) {
return b[v];
}
int tm = (tl + tr) / 2;
// If 'pos' is less than or equal to 'tm'
if (pos <= tm) {
return Math.max(get(b, v * 2, tl, tm, pos),
b[v]);
}
else {
return Math.max(
get(b, v * 2 + 1, tm + 1, tr, pos), b[v]);
}
}
public static void main(String[] args)
{
// Example usage
int[] b = new int[100]; // assuming the size of
// array 'b'
int[] vis = new int[100]; // assuming the size of
// array 'vis'
// Example update
update(b, vis, 1, 0, 10, 2, 5, 8);
// Example get
int result = get(b, 1, 0, 10, 3);
System.out.println("Result: " + result);
}
}
// This code is contributed by Utkarsh.
# Importing the required library
from typing import List
# Defining the function 'spread'
def spread(b: List[int], vis: List[int], v: int) -> None:
# If 'v' is visited
if vis[v]:
# Updating the values in the list 'b'
b[v * 2] = max(b[v], b[v * 2])
b[v * 2 + 1] = max(b[v], b[v * 2 + 1])
# Marking the elements as visited
vis[v * 2] = 1
vis[v * 2 + 1] = 1
vis[v] = 0
# Defining the function 'update'
def update(b: List[int], vis: List[int], v: int, tl: int, tr: int, l: int, r: int, val: int) -> None:
# If 'l' is greater than 'r', then return
if l > r:
return
# If 'l' is equal to 'tl' and 'r' is equal to 'tr'
if l == tl and r == tr:
# Updating the value in the list 'b'
b[v] = max(val, b[v])
# Marking the element as visited
vis[v] = 1
return
# Calling the function 'spread'
spread(b, vis, v)
tm = (tl + tr) // 2
# Recursive calls to the function 'update'
update(b, vis, v * 2, tl, tm, l, min(r, tm), val)
update(b, vis, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val)
# Defining the function 'get'
def get(b: List[int], v: int, tl: int, tr: int, pos: int) -> int:
# If 'tl' is equal to 'tr', then return the value at index 'v' in the list 'b'
if tl == tr:
return b[v]
tm = (tl + tr) // 2
# If 'pos' is less than or equal to 'tm'
if pos <= tm:
return max(get(b, v * 2, tl, tm, pos), b[v])
else:
return max(get(b, v * 2 + 1, tm + 1, tr, pos), b[v])
// Defining the function 'spread'
function spread(b, vis, v) {
// If 'v' is visited
if (vis[v] === 1) {
// Updating the values in the array 'b'
b[v * 2] = Math.max(b[v], b[v * 2]);
b[v * 2 + 1] = Math.max(b[v], b[v * 2 + 1]);
// Marking the elements as visited
vis[v * 2] = 1;
vis[v * 2 + 1] = 1;
vis[v] = 0;
}
}
// Defining the function 'update'
function update(b, vis, v, tl, tr, l, r, val) {
// If 'l' is greater than 'r', then return
if (l > r) {
return;
}
// If 'l' is equal to 'tl' and 'r' is equal to 'tr'
if (l === tl && r === tr) {
// Updating the value in the array 'b'
b[v] = Math.max(val, b[v]);
// Marking the element as visited
vis[v] = 1;
return;
}
// Calling the function 'spread'
spread(b, vis, v);
let tm = Math.floor((tl + tr) / 2);
// Recursive calls to the function 'update'
update(b, vis, v * 2, tl, tm, l, Math.min(r, tm), val);
update(b, vis, v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, val);
}
// Defining the function 'get'
function get(b, v, tl, tr, pos) {
// If 'tl' is equal to 'tr', then return the value at index 'v' in the array 'b'
if (tl === tr) {
return b[v];
}
let tm = Math.floor((tl + tr) / 2);
// If 'pos' is less than or equal to 'tm'
if (pos <= tm) {
return Math.max(get(b, v * 2, tl, tm, pos), b[v]);
} else {
return Math.max(get(b, v * 2 + 1, tm + 1, tr, pos), b[v]);
}
}
// Example usage
let b = new Array(100).fill(0); // assuming the size of array 'b'
let vis = new Array(100).fill(0); // assuming the size of array 'vis'
// Example update
update(b, vis, 1, 0, 10, 2, 5, 8);
// Example get
let result = get(b, 1, 0, 10, 3);
console.log("Result: " + result);
2.Assignment to a Segment:
Given an array of n elements, initialized with zero. The task is two process two types of queries:
- for all i from l to r do the operation ai=val,
- find the current value of element i.
The idea is to apply the update operation in such a way that operations are deeper in the tree than the newer operations.
The only difference here is that in get operation when we go from root to leaf, if a node is visited we can simply return the value of that node and there is no need to go deeper, since the newer operations are stored at the higher level. The time complexity of both gets and update operation will be O(log n).
Below is the implementation of above approach:
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
private:
vector<int> b, vis;
int size;
void spread(int v) {
if (vis[v] == 1) {
b[v * 2] = b[v];
b[v * 2 + 1] = b[v];
vis[v * 2] = 1;
vis[v * 2 + 1] = 1;
vis[v] = 0;
}
}
public:
SegmentTree(int size) : size(size) {
b.resize(4 * size);
vis.resize(4 * size);
}
void update(int v, int tl, int tr, int l, int r, int val) {
if (l > r || v >= 4 * size) return;
if (l <= tl && r >= tr) {
b[v] = val;
vis[v] = 1;
return;
}
spread(v);
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, min(r, tm), val);
update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
}
int get(int v, int tl, int tr, int pos) {
if (tl == tr) return b[v];
int tm = (tl + tr) / 2;
if (pos <= tm) {
if (vis[v] == 1) return b[v];
else return get(v * 2, tl, tm, pos);
} else {
if (vis[v] == 1) return b[v];
else return get(v * 2 + 1, tm + 1, tr, pos);
}
}
};
int main() {
int size = 10;
SegmentTree segmentTree(size);
segmentTree.update(1, 0, size - 1, 2, 5, 42);
int result = segmentTree.get(1, 0, size - 1, 3);
cout << result << endl; // Output: 42
return 0;
}
// Implementation of a Segment Tree class
class SegmentTree {
// Arrays to store segment tree nodes and visibility flags
int[] b, vis;
int size;
// Constructor to initialize the segment tree with given size
public SegmentTree(int size) {
this.size = size;
this.b = new int[4 * size]; // Update array size to accommodate all possible nodes
this.vis = new int[4 * size]; // Update array size to accommodate all possible nodes
}
// Helper function to spread values to child nodes
private void spread(int v) {
if (vis[v] == 1) {
// Spread the current value to both child nodes
b[v * 2] = b[v];
b[v * 2 + 1] = b[v];
// Mark both child nodes as visible
vis[v * 2] = 1;
vis[v * 2 + 1] = 1;
// Mark the current node as not visible
vis[v] = 0;
}
}
// Update function to modify values in the segment tree
public void update(int v, int tl, int tr, int l, int r, int val) {
// If the range is invalid, return
if (l > r || v >= 4 * size) return;
// If the current node covers the entire range, update its value and visibility
if (l <= tl && r >= tr) {
b[v] = val;
vis[v] = 1;
return;
}
// Spread the current value to child nodes
spread(v);
// Calculate the midpoint of the range
int tm = (tl + tr) / 2;
// Recursively update the left and right child nodes
update(v * 2, tl, tm, l, Math.min(r, tm), val);
update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, val);
}
// Get function to retrieve values from the segment tree
public int get(int v, int tl, int tr, int pos) {
// If the range has reduced to a single point, return the value at that point
if (tl == tr) return b[v];
// Calculate the midpoint of the range
int tm = (tl + tr) / 2;
// If the position is in the left half, recursively get the value from the left child
if (pos <= tm) {
// If the current node is marked as visible, return its value
if (vis[v] == 1) return b[v];
// Otherwise, continue searching in the left child
else return get(v * 2, tl, tm, pos);
}
// If the position is in the right half, recursively get the value from the right child
else {
// If the current node is marked as visible, return its value
if (vis[v] == 1) return b[v];
// Otherwise, continue searching in the right child
else return get(v * 2 + 1, tm + 1, tr, pos);
}
}
}
// Driver Code
public class Main {
public static void main(String[] args) {
int size = 10;
SegmentTree segmentTree = new SegmentTree(size);
segmentTree.update(1, 0, size - 1, 2, 5, 42);
int result = segmentTree.get(1, 0, size - 1, 3);
System.out.println(result); // Output: 42
}
}
class SegmentTree:
def __init__(self, size):
self.b = [0] * (4 * size) # Initialize array for segment tree values
self.vis = [0] * (4 * size) # Initialize array for marking segments as visited
self.size = size
def spread(self, v):
"""Spread the value of a parent node to its children if necessary."""
if self.vis[v] == 1:
self.b[v * 2] = self.b[v]
self.b[v * 2 + 1] = self.b[v]
self.vis[v * 2] = 1
self.vis[v * 2 + 1] = 1
self.vis[v] = 0
def update(self, v, tl, tr, l, r, val):
"""Update the segment tree with the given range and value."""
if l > r or v >= 4 * self.size:
return
if l <= tl and r >= tr:
self.b[v] = val
self.vis[v] = 1
return
self.spread(v)
tm = (tl + tr) // 2
self.update(v * 2, tl, tm, l, min(r, tm), val)
self.update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val)
def get(self, v, tl, tr, pos):
"""Get the value at the given position in the segment tree."""
if tl == tr:
return self.b[v]
tm = (tl + tr) // 2
if pos <= tm:
if self.vis[v] == 1:
return self.b[v]
else:
return self.get(v * 2, tl, tm, pos)
else:
if self.vis[v] == 1:
return self.b[v]
else:
return self.get(v * 2 + 1, tm + 1, tr, pos)
if __name__ == "__main__":
size = 10
segmentTree = SegmentTree(size)
segmentTree.update(1, 0, size - 1, 2, 5, 42)
result = segmentTree.get(1, 0, size - 1, 3)
print(result) # Output: 42
#this code is contributed by Utkarsh
// Implementation of a Segment Tree class
class SegmentTree {
// Constructor to initialize the segment tree with given size
constructor(size) {
// Arrays to store segment tree nodes and visibility flags
this.b = new Array(2 * size).fill(0);
this.vis = new Array(2 * size).fill(0);
}
// Helper function to spread values to child nodes
spread(v) {
if (this.vis[v]) {
// Spread the current value to both child nodes
this.b[v * 2] = this.b[v];
this.b[v * 2 + 1] = this.b[v];
// Mark both child nodes as visible
this.vis[v * 2] = 1;
this.vis[v * 2 + 1] = 1;
// Mark the current node as not visible
this.vis[v] = 0;
}
}
// Update function to modify values in the segment tree
update(v, tl, tr, l, r, val) {
// If the range is invalid, return
if (l > r) return;
// If the current node covers the entire range, update its value and visibility
if (l === tl && r === tr) {
this.b[v] = val;
this.vis[v] = 1;
return;
}
// Spread the current value to child nodes
this.spread(v);
// Calculate the midpoint of the range
const tm = Math.floor((tl + tr) / 2);
// Recursively update the left and right child nodes
this.update(v * 2, tl, tm, l, Math.min(r, tm), val);
this.update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, val);
}
// Get function to retrieve values from the segment tree
get(v, tl, tr, pos) {
// If the range has reduced to a single point, return the value at that point
if (tl === tr) return this.b[v];
// Calculate the midpoint of the range
const tm = Math.floor((tl + tr) / 2);
// If the position is in the left half, recursively get the value from the left child
if (pos <= tm) {
// If the current node is marked as visible, return its value
if (this.vis[v]) return this.b[v];
// Otherwise, continue searching in the left child
else return this.get(v * 2, tl, tm, pos);
}
// If the position is in the right half, recursively get the value from the right child
else {
// If the current node is marked as visible, return its value
if (this.vis[v]) return this.b[v];
// Otherwise, continue searching in the right child
else return this.get(v * 2 + 1, tm + 1, tr, pos);
}
}
}
// Driver Code
const size = 10;
const segmentTree = new SegmentTree(size);
segmentTree.update(1, 0, size - 1, 2, 5, 42);
const result = segmentTree.get(1, 0, size - 1, 3);
console.log(result);
Output
42
Range Operations and Lazy Propagation for Competitive Programming
In competitive programming, mastering range operations and understanding lazy propagation techniques is a crucial skill set for efficiently handling complex problems involving large datasets. Range operations involve performing actions, such as queries or updates, over a specific range of elements in a data structure, offering a powerful tool for solving algorithmic challenges.
Table of Content
- What is a range query?
- What is a Segment Tree?
- Why Segment Tree is not optimal for Range Operations (updates)
- Lazy Propagation for Range Operations
- Implementation for Lazy Propagation
- Use cases of Lazy Propagation in Competitive Programming
- Practice Problems on Lazy Propagation for Competitive Programming