कोडिंग साक्षात्कार की तैयारी · पाठ

Range Updates के लिए Lazy Propagation

पूरी ranges पर updates को बाद के लिए टालें

पाठ 4, कुल 4 में से13 चरण

Range Updates के लिए Lazy Propagation, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

परास-अद्यतन की समस्या

यदि कोई क्वेरी l से r तक के हर तत्व में 5 जोड़ने को कहे तो? हर पत्ती को छूने में प्रत्येक अद्यतन पर O(n) समय लगेगा, जो बहुत सारे परास-अद्यतनों के लिए अत्यंत धीमा है। 😰

विलंबित प्रसार का विचार

विलंबित प्रसार किसी नोड को लंबित बदलाव याद रखने देता है, बिना उसे अभी बच्चों तक भेजे। काम तब तक टाला जाता है जब तक आपको वास्तव में उन बच्चों की आवश्यकता न हो।

लंबित काम के लिए दूसरी सरणी

वृक्ष के साथ हम एक विलंबित सरणी रखते हैं। lazy[node] उस नोड के पूरे परास पर लागू होने वाला ऐसा अद्यतन रखता है जिसे अभी नीचे नहीं भेजा गया है।

lazy = [0] * (4 * n)

पूरे नोड पर लागू करें

जब कोई अद्यतन किसी नोड को पूरी तरह ढकता है, तो उसके संग्रहीत मान को समायोजित करें और बदलाव को विलंबित में रख दें, फिर रुक जाएँ। नीचे जाने की आवश्यकता नहीं है।

seg[node] += (r - l + 1) * val
lazy[node] += val

नीचे जाने से पहले नीचे भेजें

बच्चों पर जाने से पहले किसी भी लंबित विलंबित मान को दोनों बच्चों में नीचे भेजें। इससे बच्चे ठीक उसी समय सही रहते हैं जब आप उन्हें पढ़ते हैं।

def push_down(node, l, r):
    if lazy[node]:
        apply(2*node, l, mid)
        apply(2*node+1, mid+1, r)
        lazy[node] = 0

हर नोड के लिए तीन स्थितियाँ

हर नोड पर क्वेरी-परास असंबद्ध, पूरी तरह समाविष्ट या आंशिक हो सकता है। क्रमशः छोड़ें, विलंबित रूप से लागू करें या दोनों हिस्सों में पुनरावर्ती रूप से जाएँ।

विलंबित अद्यतन लघुगणकीय रहते हैं

परास-अद्यतन केवल O(log n) नोडों को छूता है, क्योंकि पूरी तरह समाविष्ट नोडों पर काम जल्दी रुक जाता है। यही विलंबित प्रसार का पूरा लाभ है। ⚡

परास प्रश्नों को भी नीचे भेजें

पुनरावर्तन में जाने से पहले परास प्रश्नों को भी नीचे भेजना आवश्यक है, ताकि वे बच्चों के ताज़ा मान पढ़ें। इसे भूल जाना विलंबित प्रसार की आम गलती है।

पुनरावर्तन के बाद ऊपर समेकित करें

बच्चों को अद्यतन करने के बाद, उनसे जनक को फिर से संयोजित करें। यह ऊपर का समेकन प्रत्येक आंतरिक नोड को उसके उपवृक्ष के अनुरूप रखता है।

seg[node] = seg[2*node] + seg[2*node+1]

मान-निर्धारण और जोड़

विलंबित प्रसार कई संक्रियाओं के लिए काम करता है, लेकिन मान-निर्धारण और जोड़ अलग-अलग तरह से संयोजित होते हैं। कोड लिखने से पहले तय करें कि दो लंबित अद्यतन कैसे मिलेंगे।

विलंबित प्रसार कब उपयोगी है

विलंबित प्रसार का उपयोग तभी करें जब आपको वास्तव में परास अद्यतन चाहिए हों। केवल बिंदु अद्यतनों के लिए साधारण खंड-वृक्ष अधिक सरल और पर्याप्त है।

त्वरित जाँच

किसी नोड के बच्चों में पुनरावर्तन करने से पहले क्या होना आवश्यक है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन: स्थगित अद्यतन

आपने विलंबित प्रसार सीखा: लंबित परिवर्तनों को संग्रहीत करें, नीचे जाने से पहले उन्हें नीचे भेजें, लौटने के बाद ऊपर समेकित करें और O(log n) परास अद्यतन प्राप्त करें। 🎉

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Range Updates के लिए Lazy Propagation” पाठ निःशुल्क है?

हाँ—“Range Updates के लिए Lazy Propagation” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Range Updates के लिए Lazy Propagation” में मैं क्या सीखूँगा?

पूरी ranges पर updates को बाद के लिए टालें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।

“Range Updates के लिए Lazy Propagation” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ