Updating an interval (Lazy propagation)
Lazy Propagation: A speedup technique for range updates
- We can delay some updates (avoid recursive calls in update) and do such updates only when necessary when there are several updates and updates are being performed on a range.
- A node in a segment tree stores or displays the results of a query for a variety of indexes.
- Additionally, all of the node’s descendants must also be updated if the update operation’s range includes this node.
- Take the node with the value 27 in the picture above as an example. This node contains the sum of values at the indexes 3 to 5. This node and all of its descendants must be updated if our update query covers the range of 2 to 5.
- By storing this update information in distinct nodes referred to as lazy nodes or values, we use lazy propagation to update only the node with value 27 and delay updates to its descendants.
- We make an array called lazy[] to stand in for the lazy node. The size of lazy[] is the same as the array used to represent the segment tree in the code following, which is tree[].
- The goal is to set all of the lazy[elements] to 0.
- There are no pending changes on the segment tree node i if lazy[i] has a value of 0.
- A non-zero value for lazy[i] indicates that before doing any queries on node i in the segment tree, this sum needs to be added to the node.
Below is the implementation to demonstrate the working of Lazy Propagation.
C++
// Program to show segment tree to // demonstrate lazy propagation #include <bits/stdc++.h> using namespace std; #define MAX 1000 // Ideally, we should not use global // variables and large constant-sized // arrays, we have done it here for // simplicity. // To store segment tree int tree[MAX] = { 0 }; // To store pending updates int lazy[MAX] = { 0 }; // si -> index of current node in segment tree // ss and se -> Starting and ending // indices of elements for which current // nodes stores sum. // us and ue -> starting and ending indexes // of update query // diff -> which we need to add in the // range us to ue void updateRangeUtil( int si, int ss, int se, int us, int ue, int diff) { // If lazy value is non-zero for // current node of segment tree, then // there are some pending updates. So, // we need to make sure that the // pending updates are done before // making new updates. Because this // value may be used by parent after // recursive calls (See last line // of this function) if (lazy[si] != 0) { // Make pending updates using // value stored in lazy nodes tree[si] += (se - ss + 1) * lazy[si]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // We can postpone updating // children we don't need // their new values now. Since // we are not yet updating // children of si, we need to // set lazy flags for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // Set the lazy value for current // node as 0 as it has been updated lazy[si] = 0; } // out of range if (ss > se || ss > ue || se < us) return ; // Current segment is fully in range if (ss >= us && se <= ue) { // Add the difference to // current node tree[si] += (se - ss + 1) * diff; // Same logic for checking // leaf node or not if (ss != se) { // This is where we store // values in lazy nodes, // rather than updating the // segment tree itself Since // we don't need these updated // values now we postpone // updates by storing values // in lazy[] lazy[si * 2 + 1] += diff; lazy[si * 2 + 2] += diff; } return ; } // If not completely in rang, // but overlaps, recur for children, int mid = (ss + se) / 2; updateRangeUtil(si * 2 + 1, ss, mid, us, ue, diff); updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, diff); // And use the result of children // calls to update this node tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to update a range of values // in segment tree // us and eu -> starting and ending // indices of update query // ue -> ending index of update query // diff -> which we need to add in the // range us to ue void updateRange( int n, int us, int ue, int diff) { updateRangeUtil(0, 0, n - 1, us, ue, diff); } // A recursive function to get the sum of // values in given range of the array. // The following are parameters for this function. // si --> Index of current node in the st. // Initially 0 is passed as root is always // at' index 0 // ss & se --> Starting and ending indices // of the segment represented by current // node, i.e., tree[si] // qs & qe --> Starting and ending // indices of query range int getSumUtil( int ss, int se, int qs, int qe, int si) { // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before // processing the sub sum query if (lazy[si] != 0) { // Make pending updates to this // node. Note that this node // represents sum of elements in // arr[ss..se] and all these // elements must be increased by // lazy[si] tree[si] += (se - ss + 1) * lazy[si]; // Checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // Since we are not yet // updating children os si, // we need to set lazy values // for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // unset the lazy value for current // node as it has been updated lazy[si] = 0; } // Out of range if (ss > se || ss > qe || se < qs) return 0; // At this point we are sure that // pending lazy updates are done for // current node. So we can return // value // If this segment lies in range if (ss >= qs && se <= qe) return tree[si]; // If a part of this segment overlaps // with the given range int mid = (ss + se) / 2; return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); } // Return sum of elements in range from // index qs (query start) to qe (query end). // It mainly uses getSumUtil() int getSum( int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { cout << "Invalid Input" ; return -1; } return getSumUtil(0, n - 1, qs, qe, 0); } // A recursive function that constructs // Segment Tree for array[ss..se]. // si is index of current node in st. void constructSTUtil( int arr[], int ss, int se, int si) { // Out of range as ss can never // be greater than se if (ss > se) return ; // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { tree[si] = arr[ss]; return ; } // If there are more than one elements, // then recur for left and right // subtrees and store the sum of // values in this node int mid = (ss + se) / 2; constructSTUtil(arr, ss, mid, si * 2 + 1); constructSTUtil(arr, mid + 1, se, si * 2 + 2); tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to construct segment tree // from given array.This function allocates // memory for segment tree and calls // constructSTUtil() to fill the // allocated memory void constructST( int arr[], int n) { // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, 0); } // Driver program to test above functions int main() { int arr[] = { 1, 3, 5, 7, 9, 11 }; int n = sizeof (arr) / sizeof (arr[0]); // Build segment tree from given array constructST(arr, n); // Print sum of values in array // from index 1 to 3 cout << "Sum of values in given range = " << getSum(n, 1, 3) << endl; // Add 10 to all nodes at indexes // from 1 to 5. updateRange(n, 1, 5, 10); // Find sum after the value is updated cout << "Updated sum of values in given range = " << getSum(n, 1, 3) << endl; return 0; } |
Java
// Java program to show segment tree to // demonstrate lazy propagation import java.util.*; class GFG { // Ideally, we should not use global // variables and large constant-sized // arrays, we have done it here for // simplicity. static final int MAX = 1000 ; // To store segment tree static int [] tree = new int [MAX]; // To store pending updates static int [] lazy = new int [MAX]; // si -> index of current node in segment tree // ss and se -> Starting and ending // indices of elements for which current // nodes stores sum. // us and ue -> starting and ending indexes // of update query // diff -> which we need to add in the // range us to ue static void updateRangeUtil( int si, int ss, int se, int us, int ue, int diff) { // If lazy value is non-zero for // current node of segment tree, then // there are some pending updates. So, // we need to make sure that the // pending updates are done before // making new updates. Because this // value may be used by parent after // recursive calls (See last line // of this function) if (lazy[si] != 0 ) { // Make pending updates using // value stored in lazy nodes tree[si] += (se - ss + 1 ) * lazy[si]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // We can postpone updating // children we don't need // their new values now. Since // we are not yet updating // children of si, we need to // set lazy flags for the children lazy[si * 2 + 1 ] += lazy[si]; lazy[si * 2 + 2 ] += lazy[si]; } // Set the lazy value for current // node as 0 as it has been updated lazy[si] = 0 ; } // out of range if (ss > se || ss > ue || se < us) { return ; } // Current segment is fully in range if (ss >= us && se <= ue) { // Add the difference to // current node tree[si] += (se - ss + 1 ) * diff; // Same logic for checking // leaf node or not if (ss != se) { // This is where we store // values in lazy nodes, // rather than updating the // segment tree itself Since // we don't need these updated // values now we postpone // updates by storing values // in lazy[] lazy[si * 2 + 1 ] += diff; lazy[si * 2 + 2 ] += diff; } return ; } // If not completely in rang, // but overlaps, recur for children, int mid = (ss + se) / 2 ; updateRangeUtil(si * 2 + 1 , ss, mid, us, ue, diff); updateRangeUtil(si * 2 + 2 , mid + 1 , se, us, ue, diff); // And use the result of children // calls to update this node tree[si] = tree[si * 2 + 1 ] + tree[si * 2 + 2 ]; } // Function to update a range of values // in segment tree // us and eu -> starting and ending // indices of update query // ue -> ending index of update query // diff -> which we need to add in the // range us to ue static void updateRange( int n, int us, int ue, int diff) { updateRangeUtil( 0 , 0 , n - 1 , us, ue, diff); } // A recursive function to get the sum of // values in given range of the array. // The following are parameters for this function. // si --> Index of current node in the st. // Initially 0 is passed as root is always // at' index 0 // ss & se --> Starting and ending indices // of the segment represented by current // node, i.e., tree[si] // qs & qe --> Starting and ending // indices of query range static int getSumUtil( int ss, int se, int qs, int qe, int si) { // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before // processing the sub sum query if (lazy[si] != 0 ) { // Make pending updates to this // node. Note that this node // represents sum of elements in // arr[ss..se] and all these // elements must be increased by // lazy[si] tree[si] += (se - ss + 1 ) * lazy[si]; // Checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // Since we are not yet // updating children os si, // we need to set lazy values // for the children lazy[si * 2 + 1 ] += lazy[si]; lazy[si * 2 + 2 ] += lazy[si]; } // unset the lazy value for current // node as it has been updated lazy[si] = 0 ; } // Out of range if (ss > se || ss > qe || se < qs) { return 0 ; } // At this point we are sure that // pending lazy updates are done for // current node. So we can return // value // If this segment lies in range if (ss >= qs && se <= qe) { return tree[si]; } // If a part of this segment overlaps // with the given range int mid = (ss + se) / 2 ; return getSumUtil(ss, mid, qs, qe, 2 * si + 1 ) + getSumUtil(mid + 1 , se, qs, qe, 2 * si + 2 ); } // Return sum of elements in range from // index qs (query start) to qe (query end). // It mainly uses getSumUtil() static int getSum( int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { System.out.println( "Invalid Input" ); return - 1 ; } return getSumUtil( 0 , n - 1 , qs, qe, 0 ); } // A recursive function that constructs // Segment Tree for array[ss..se]. // si is index of current node in st. static void constructSTUtil( int arr[], int ss, int se, int si) { // Out of range as ss can never // be greater than se if (ss > se) return ; // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { tree[si] = arr[ss]; return ; } // If there are more than one elements, // then recur for left and right // subtrees and store the sum of // values in this node int mid = (ss + se) / 2 ; constructSTUtil(arr, ss, mid, si * 2 + 1 ); constructSTUtil(arr, mid + 1 , se, si * 2 + 2 ); tree[si] = tree[si * 2 + 1 ] + tree[si * 2 + 2 ]; } // Function to construct segment tree // from given array.This function allocates // memory for segment tree and calls // constructSTUtil() to fill the // allocated memory static void constructST( int arr[], int n) { // Fill the allocated memory st constructSTUtil(arr, 0 , n - 1 , 0 ); } // Driver program to test above functions public static void main(String[] args) { int arr[] = { 1 , 3 , 5 , 7 , 9 , 11 }; int n = arr.length; // Build segment tree from given array constructST(arr, n); // Print sum of values in array // from index 1 to 3 System.out.println( "Sum of values in given range = " + getSum(n, 1 , 3 )); // Add 10 to all nodes at indexes // from 1 to 5. updateRange(n, 1 , 5 , 10 ); // Find sum after the value is updated System.out.println( "Updated sum of values in given range = " + getSum(n, 1 , 3 )); } } // This code is contributed by Prasad Kandekar(prasad264) |
Python3
# Program to show segment tree to # demonstrate lazy propagation MAX = 1000 # Ideally, we should not use global # variables and large constant-sized # arrays, we have done it here for # simplicity. # To store segment tree tree = [ 0 ] * MAX # To store pending updates lazy = [ 0 ] * MAX # si -> index of current node in segment tree # ss and se -> Starting and ending # indices of elements for which current # nodes stores sum. # us and ue -> starting and ending indexes # of update query # diff -> which we need to add in the # range us to ue def updateRangeUtil(si, ss, se, us, ue, diff): # If lazy value is non-zero for # current node of segment tree, then # there are some pending updates. So, # we need to make sure that the # pending updates are done before # making new updates. Because this # value may be used by parent after # recursive calls (See last line # of this function) if lazy[si] ! = 0 : # Make pending updates using # value stored in lazy nodes tree[si] + = (se - ss + 1 ) * lazy[si] # checking if it is not leaf node # because if it is leaf node then # we cannot go further if ss ! = se: # We can postpone updating # children we don't need # their new values now. Since # we are not yet updating # children of si, we need to # set lazy flags for the children lazy[si * 2 + 1 ] + = lazy[si] lazy[si * 2 + 2 ] + = lazy[si] # Set the lazy value for current # node as 0 as it has been updated lazy[si] = 0 # out of range if ss > se or ss > ue or se < us: return # Current segment is fully in range if ss > = us and se < = ue: # Add the difference to # current node tree[si] + = (se - ss + 1 ) * diff # Same logic for checking # leaf node or not if ss ! = se: # This is where we store # values in lazy nodes, # rather than updating the # segment tree itself Since # we don't need these updated # values now we postpone # updates by storing values # in lazy[] lazy[si * 2 + 1 ] + = diff lazy[si * 2 + 2 ] + = diff return # If not completely in rang, # but overlaps, recur for children, mid = (ss + se) / / 2 updateRangeUtil(si * 2 + 1 , ss, mid, us, ue, diff) updateRangeUtil(si * 2 + 2 , mid + 1 , se, us, ue, diff) # And use the result of children # calls to update this node tree[si] = tree[si * 2 + 1 ] + tree[si * 2 + 2 ] # Function to update a range of values # in segment tree # us and eu -> starting and ending # indices of update query # ue -> ending index of update query # diff -> which we need to add in the # range us to ue def updateRange(n, us, ue, diff): updateRangeUtil( 0 , 0 , n - 1 , us, ue, diff) # A recursive function to get the sum of # values in given range of the array. # The following are parameters for this function. # si --> Index of current node in the st. # Initially 0 is passed as root is always # at' index 0 # ss & se --> Starting and ending indices # of the segment represented by current # node, i.e., tree[si] # qs & qe --> Starting and ending # indices of query range def getSumUtil(ss, se, qs, qe, si): # If lazy flag is set for current # node of segment tree, then there # are some pending updates. So we # need to make sure that the pending # updates are done before # processing the sub sum query if lazy[si] ! = 0 : # Make pending updates to this # node. Note that this node # represents sum of elements in # arr[ss..se] and all these # elements must be increased by # lazy[si] tree[si] + = (se - ss + 1 ) * lazy[si] # Checking if it is not leaf node # because if it is leaf node then # we cannot go further if ss ! = se: # Since we are not yet # updating children os si, # we need to set lazy values # for the children lazy[si * 2 + 1 ] + = lazy[si] lazy[si * 2 + 2 ] + = lazy[si] # unset the lazy value for current # node as it has been updated lazy[si] = 0 # Out of range if ss > se or ss > qe or se < qs: return 0 # At this point we are sure that # pending lazy updates are done for # current node. So we can return # value # If this segment lies in range if ss > = qs and se < = qe: return tree[si] # If a part of this segment overlaps # with the given range mid = (ss + se) / / 2 return (getSumUtil(ss, mid, qs, qe, 2 * si + 1 ) + getSumUtil(mid + 1 , se, qs, qe, 2 * si + 2 )) # Return sum of elements in range from # index qs (query start) to qe (query end). # It mainly uses getSumUtil() def getSum(n, qs, qe): # Check for erroneous input values if qs < 0 or qe > n - 1 or qs > qe: print ( "Invalid Input" ) return - 1 return getSumUtil( 0 , n - 1 , qs, qe, 0 ) # A recursive function that constructs # Segment Tree for array[ss..se]. # si is index of current node in st. def constructSTUtil(arr, ss, se, si): # Out of range as ss can never # be greater than se if ss > se: return # If there is one element in array, # store it in current node of segment # tree and return if ss = = se: tree[si] = arr[ss] return # If there are more than one elements, # then recur for left and right # subtrees and store the sum of # values in this node mid = (ss + se) / / 2 constructSTUtil(arr, ss, mid, si * 2 + 1 ) constructSTUtil(arr, mid + 1 , se, si * 2 + 2 ) tree[si] = tree[si * 2 + 1 ] + tree[si * 2 + 2 ] # Function to construct segment tree # from given array.This function allocates # memory for segment tree and calls # constructSTUtil() to fill the # allocated memory def constructST(arr, n): # Fill the allocated memory st constructSTUtil(arr, 0 , n - 1 , 0 ) # Driver program to test above functions arr = [ 1 , 3 , 5 , 7 , 9 , 11 ] n = len (arr) # Build segment tree from given array constructST(arr, n) # Print sum of values in array # from index 1 to 3 print (f "Sum of values in given range = {getSum(n, 1, 3)}" ) # Add 10 to all nodes at indexes # from 1 to 5. updateRange(n, 1 , 5 , 10 ) # Find sum after the value is updated print (f "Updated sum of values in given range = {getSum(n, 1, 3)}" ) |
C#
// Program to show segment tree to // demonstrate lazy propagation using System; public class GFG { const int MAX = 1000; // Ideally, we should not use global // variables and large constant-sized // arrays, we have done it here for // simplicity. // To store segment tree static int [] tree = new int [MAX]; // To store pending updates static int [] lazy = new int [MAX]; // si -> index of current node in segment tree // ss and se -> Starting and ending // indices of elements for which current // nodes stores sum. // us and ue -> starting and ending indexes // of update query // diff -> which we need to add in the // range us to ue static void UpdateRangeUtil( int si, int ss, int se, int us, int ue, int diff) { // If lazy value is non-zero for // current node of segment tree, then // there are some pending updates. So, // we need to make sure that the // pending updates are done before // making new updates. Because this // value may be used by parent after // recursive calls (See last line // of this function) if (lazy[si] != 0) { // Make pending updates using // value stored in lazy nodes tree[si] += (se - ss + 1) * lazy[si]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // We can postpone updating // children we don't need // their new values now. Since // we are not yet updating // children of si, we need to // set lazy flags for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // Set the lazy value for current // node as 0 as it has been updated lazy[si] = 0; } // out of range if (ss > se || ss > ue || se < us) return ; // Current segment is fully in range if (ss >= us && se <= ue) { // Add the difference to // current node tree[si] += (se - ss + 1) * diff; // Same logic for checking // leaf node or not if (ss != se) { // This is where we store // values in lazy nodes, // rather than updating the // segment tree itself Since // we don't need these updated // values now we postpone // updates by storing values // in lazy[] lazy[si * 2 + 1] += diff; lazy[si * 2 + 2] += diff; } return ; } // If not completely in rang, // but overlaps, recur for children, int mid = (ss + se) / 2; UpdateRangeUtil(si * 2 + 1, ss, mid, us, ue, diff); UpdateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, diff); // And use the result of children // calls to update this node tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to update a range of values // in segment tree // us and eu -> starting and ending // indices of update query // ue -> ending index of update query // diff -> which we need to add in the // range us to ue static void UpdateRange( int n, int us, int ue, int diff) { UpdateRangeUtil(0, 0, n - 1, us, ue, diff); } // A recursive function to get the sum of // values in given range of the array. // The following are parameters for this function. // si --> Index of current node in the st. // Initially 0 is passed as root is always // at' index 0 // ss & se --> Starting and ending indices // of the segment represented by current // node, i.e., tree[si] // qs & qe --> Starting and ending // indices of query range static int GetSumUtil( int ss, int se, int qs, int qe, int si) { // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before // processing the sub sum query if (lazy[si] != 0) { // Make pending updates to this // node. Note that this node // represents sum of elements in // arr[ss..se] and all these // elements must be increased by // lazy[si] tree[si] += (se - ss + 1) * lazy[si]; // Checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // Since we are not yet // updating children os si, // we need to set lazy values // for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // unset the lazy value for current // node as it has been updated lazy[si] = 0; } // Out of range if (ss > se || ss > qe || se < qs) return 0; // At this point we are sure that // pending lazy updates are done for // current node. So we can return // value // If this segment lies in range if (ss >= qs && se <= qe) return tree[si]; // If a part of this segment overlaps // with the given range int mid = (ss + se) / 2; return GetSumUtil(ss, mid, qs, qe, 2 * si + 1) + GetSumUtil(mid + 1, se, qs, qe, 2 * si + 2); } // Return sum of elements in range from // index qs (query start) to qe (query end). // It mainly uses getSumUtil() static int GetSum( int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { Console.WriteLine( "Invalid Input" ); return -1; } return GetSumUtil(0, n - 1, qs, qe, 0); } // A recursive function that constructs // Segment Tree for array[ss..se]. // si is index of current node in st. static void ConstructSTUtil( int [] arr, int ss, int se, int si) { // Out of range as ss can never // be greater than se if (ss > se) return ; // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { tree[si] = arr[ss]; return ; } // If there are more than one elements, // then recur for left and right // subtrees and store the sum of // values in this node int mid = (ss + se) / 2; ConstructSTUtil(arr, ss, mid, si * 2 + 1); ConstructSTUtil(arr, mid + 1, se, si * 2 + 2); tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to construct segment tree // from given array.This function allocates // memory for segment tree and calls // constructSTUtil() to fill the // allocated memory static void ConstructST( int [] arr, int n) { // Fill the allocated memory st ConstructSTUtil(arr, 0, n - 1, 0); } // Driver program to test above functions static public void Main( string [] args) { int [] arr = { 1, 3, 5, 7, 9, 11 }; int n = arr.Length; // Build segment tree from given array ConstructST(arr, n); // Print sum of values in array // from index 1 to 3 Console.WriteLine( "Sum of values in given range = " + GetSum(n, 1, 3)); // Add 10 to all nodes at indexes // from 1 to 5. UpdateRange(n, 1, 5, 10); // Find sum after the value is updated Console.WriteLine( "Updated sum of values in given range = " + GetSum(n, 1, 3)); } } // This code is contributed by Prasad Kandekar(prasad264) |
Javascript
//javascript Program to show segment tree to // demonstrate lazy propagation let MAX = 1000; // Ideally, we should not use global // variables and large constant-sized // arrays, we have done it here for // simplicity. // To store segment tree let tree = new Array(MAX).fill(0); // To store pending updates let lazy = new Array(MAX).fill(0); // si -> index of current node in segment tree // ss and se -> Starting and ending // indices of elements for which current // nodes stores sum. // us and ue -> starting and ending indexes // of update query // diff -> which we need to add in the // range us to ue function updateRangeUtil( si,ss, se, us, ue, diff) { // console.log(si,ss,se,us,ue,diff); // If lazy value is non-zero for // current node of segment tree, then // there are some pending updates. So, // we need to make sure that the // pending updates are done before // making new updates. Because this // value may be used by parent after // recursive calls (See last line // of this function) if (lazy[si] != 0) { // Make pending updates using // value stored in lazy nodes tree[si] += (se - ss + 1) * lazy[si]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // We can postpone updating // children we don't need // their new values now. Since // we are not yet updating // children of si, we need to // set lazy flags for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // Set the lazy value for current // node as 0 as it has been updated lazy[si] = 0; } // out of range if (ss > se || ss > ue || se < us) return ; // Current segment is fully in range if (ss >= us && se <= ue) { // Add the difference to // current node tree[si] += (se - ss + 1) * diff; // Same logic for checking // leaf node or not if (ss != se) { // This is where we store // values in lazy nodes, // rather than updating the // segment tree itself Since // we don't need these updated // values now we postpone // updates by storing values // in lazy[] lazy[si * 2 + 1] += diff; lazy[si * 2 + 2] += diff; } return ; } // If not completely in rang, // but overlaps, recur for children, let mid = (ss + se) / 2; updateRangeUtil(Math.floor(si * 2 + 1), Math.floor(ss), Math.floor(mid), Math.floor(us), Math.floor(ue), Math.floor(diff)); updateRangeUtil(Math.floor(si * 2 + 2), Math.floor(mid + 1), Math.floor(se), Math.floor(us), Math.floor(ue), Math.floor(diff)); // And use the result of children // calls to update this node tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to update a range of values // in segment tree // us and eu -> starting and ending // indices of update query // ue -> ending index of update query // diff -> which we need to add in the // range us to ue function updateRange(n, us, ue, diff) { updateRangeUtil(0, 0, n - 1, us, ue, diff); } // A recursive function to get the sum of // values in given range of the array. // The following are parameters for this function. // si --> Index of current node in the st. // Initially 0 is passed as root is always // at' index 0 // ss & se --> Starting and ending indices // of the segment represented by current // node, i.e., tree[si] // qs & qe --> Starting and ending // indices of query range function getSumUtil( ss, se, qs, qe, si) { // console.log(ss,se,qs,qe,si); // // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before // processing the sub sum query if (lazy[si] != 0) { // Make pending updates to this // node. Note that this node // represents sum of elements in // arr[ss..se] and all these // elements must be increased by // lazy[si] tree[si] += (se - ss + 1) * lazy[si]; // Checking if it is not leaf node // because if it is leaf node then // we cannot go further if (ss != se) { // Since we are not yet // updating children os si, // we need to set lazy values // for the children lazy[si * 2 + 1] += lazy[si]; lazy[si * 2 + 2] += lazy[si]; } // unset the lazy value for current // node as it has been updated lazy[si] = 0; } // Out of range if (ss > se || ss > qe || se < qs) return 0; // At this point we are sure that // pending lazy updates are done for // current node. So we can return // value // If this segment lies in range if (ss >= qs && se <= qe) return tree[si]; // If a part of this segment overlaps // with the given range let mid = (ss + se) / 2; return getSumUtil(Math.floor(ss), Math.floor(mid), Math.floor(qs), Math.floor(qe), Math.floor(2 * si + 1)) + getSumUtil(Math.floor(mid + 1), Math.floor(se), Math.floor(qs), Math.floor(qe), Math.floor(2 * si + 2)); } // Return sum of elements in range from // index qs (query start) to qe (query end). // It mainly uses getSumUtil() function getSum (n, qs, qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { console.log( "Invalid Input" ); return -1; } // console.log(n,qs,qe); return getSumUtil(0, n - 1, qs, qe, 0); } // A recursive function that constructs // Segment Tree for array[ss..se]. // si is index of current node in st. function constructSTUtil( arr, ss, se, si) { // console.log(arr,ss,se,si); // Out of range as ss can never // be greater than se if (ss > se) return ; // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { tree[si] = arr[ss]; return ; } // If there are more than one elements, // then recur for left and right // subtrees and store the sum of // values in this node let mid = (ss + se) / 2; constructSTUtil(arr, Math.floor(ss), Math.floor(mid), Math.floor(si * 2 + 1)); constructSTUtil(arr, Math.floor(mid + 1), Math.floor(se), Math.floor(si * 2 + 2)); tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2]; } // Function to construct segment tree // from given array.This function allocates // memory for segment tree and calls // constructSTUtil() to fill the // allocated memory function constructST(arr, n) { // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, 0); } let arr = [ 1, 3, 5, 7, 9, 11 ]; let n = arr.length; // Build segment tree from given array constructST(arr, n); // Print sum of values in array // from index 1 to 3 console.log(`Sum of values in given range = ${getSum(n, 1, 3)}`); // Add 10 to all nodes at indexes // from 1 to 5. updateRange(n, 1, 5, 10); console.log(`Updated sum of values in given range = ${ getSum(n, 1, 3)}`); // This code is contributed by ksam24000. |
Output
Sum of values in given range = 15 Updated sum of values in given range = 45
Time Complexity: O(N)
Auxiliary Space: O(MAX)