Range Update Query | Lazy Propagation | Segment Tree Concepts & Qns | Video 7 | codestorywithMIK

Channel:

codestorywithMIK

Subscribers:

92,300

Published on July 7, 2024 12:00:00 AM ● Video Link: https://www.youtube.com/watch?v=FB_LjtTQwlw

Duration: 49:06

2,232 views

103

iPad PDF Notes - https://github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 7th video of our playlist "Segment Tree Concepts & Questions". Find the Details below :

Video Name : Range Update Query | Lazy Propagation | Segment Tree Concepts & Qns | Video 7 | codestorywithMIK
Video # : 7

🔍 Unraveling Segment Tree : A Journey into the Depths of it.

🎥 Welcome to the 7th Video of my Segment Tree Concepts & Questions Playlist! 🚀 In this enlightening video, we will finally start solving Qns on Segment Tree. In this one, we will solve - Range Update Query | Lazy Propagation | Segment Tree Concepts & Qns | Video 7 | codestorywithMIK

🔍 What's Inside ?

🔗 We will see how we can use Segment Tree concepts to easily solve this problem - Range Update Query | Lazy Propagation | Segment Tree Concepts & Qns | Video 7 | codestorywithMIK

👩‍💻 Who Should Watch ?

This playlist is for everyone but best suited for Freshers who are new to Segment Tree.

🚀 Embark on the Segment Tree Adventure Now!

Problem Name : Range Update Query | Lazy Propagation | Segment Tree Concepts & Qns | Video 7 | codestorywithMIK
Company Tags : Google and many other companies ask problems based on this topic
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
GfG Link : https://www.geeksforgeeks.org/lazy-pr...


My DP Concepts Playlist :    • Roadmap for DP | How to Start DP ? | ...  
My Graph Concepts Playlist :    • Graph Concepts & Qns - 1 : Graph will...  
My Recursion Concepts Playlist :    • Introduction | Recursion Concepts And...  
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Subscribe to my channel :    / @codestorywithmik  
Instagram :   / codestorywithmik  
Facebook :   / 100090524295846  
Twitter :   / cswithmik  


Summary :
The provided code implements a segment tree with lazy propagation for efficiently updating a range of values and querying the sum over a range. Here's a brief summary:

Time and Space Complexity

Time Complexity (T.C): O(logn)
Space Complexity (S.C): O(n)
Segment Tree and Lazy Propagation

Segment Tree: An array representation of the segment tree where each node stores the sum of a segment of the array.
Lazy Tree: An auxiliary array that helps in propagating updates to avoid unnecessary updates to nodes that don't need immediate updates.
Function updateRange

This function updates a given range [start, end] by adding a specified value val to all elements within that range.

Lazy Propagation:

If there is a pending update in the lazyTree for the current node (lazyTree[i] != 0), it is applied to segTree[i].
If the current node is not a leaf node, propagate the pending update to its children in the lazyTree.
Reset the current node's lazy value to 0.
Range Check:

If the current range [l, r] is completely outside the update range [start, end], return without doing anything.
If the current range [l, r] is completely inside the update range [start, end], update segTree[i] and propagate the update to its children in lazyTree.
Partial Overlap:

If there is a partial overlap, recursively call updateRange for the left and right children.
After updating the children, update the current node's value to the sum of its children.
Key Operations:

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction
00:11 - Motivation
01:49 - Recap of Point Update Query
06:42 - How to do Range Update using Lazy Propagation
36:19 - Story To Code

#codestorywithMIK
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear #RecursionExplained #CodingJourney #Programming101 #TechTalks #AlgorithmMastery #Recursion #Programming #Algorithm #Code #ComputerScience #SoftwareDevelopment #CodingTips #RecursiveFunctions #TechExplained #ProgrammingConcepts #CodeTutorial #LearnToCode #TechEducation #DeveloperCommunity #RecursiveThinking #ProgrammingLogic #ProblemSolving #AlgorithmDesign #CSEducation
#segmenttree #segment #rangequeries