Range Updates के लिए Difference Arrays

संचयी योगों ने परास के प्रश्नों का तेज़ी से उत्तर दिया। अंतर सारणी इसी विचार को उलटकर कई परास अपडेट तेज़ी से लागू करती है। 🔁

किसी परास के हर तत्व में कोई मान जोड़ना और इसे कई बार दोहराना, हर अपडेट में O(n) समय लेता है। q अपडेट में यह लागत बहुत बढ़ जाती है।

हर खाने को छूने के बजाय केवल यह दर्ज करें कि बदलाव कहाँ शुरू होता है और कहाँ समाप्त होता है। बीच के हिस्से के बजाय किनारों को चिह्नित करें।

एक अंतर सारणी प्रत्येक तत्व और उससे पहले वाले तत्व के बीच का अंतर रखती है। एक अंतर बदलने से उसके बाद का पूरा भाग प्रभावित हो जाता है।

l से r तक v जोड़ने के लिए, सूचकांक l पर v जोड़ें और सूचकांक r + 1 पर v घटाएँ। केवल दो बदलाव पूरे परास को संभाल लेते हैं।

l पर किया गया जोड़ बदलाव को चालू करता है; r + 1 पर किया गया घटाव उसे फिर बंद कर देता है। दोनों मिलकर अपडेट को एक ही परास तक सीमित रखते हैं।

हर अपडेट में केवल दो सारणी-लेखन होते हैं, इसलिए q अपडेट की कुल लागत O(q) होती है। मुख्य काम अंत तक टाल दिया जाता है।

सभी चिह्न रखने के बाद अंतर सारणी का संचयी योग निकालें। यह एकल चरण हर अंतिम मान को फिर से बना देता है।

सारणी को एक खाना अतिरिक्त रखकर बनाएँ, ताकि r + 1 कभी सीमा से बाहर न जाए। यह अतिरिक्त सुरक्षा स्थान सूचकांक-संबंधी त्रुटियों से बचाता है।

अपडेट चिह्नित करने में O(q) समय और पुनर्निर्माण के लिए एक O(n) चरण लगता है। संयुक्त लागत सीधे O(n गुणा q) करने से बहुत कम होती है।

अंतर सारणियाँ आरक्षण की गिनतियों, सड़क-करों और ऐसे सभी प्रश्नों में उपयोगी हैं जिनमें बहुत से परास-जोड़ संचालन और अंत में एक बार पढ़ना हो।

आप अंतर सारणी से परास अपडेट को एक साथ संभाल सकते हैं: l और r + 1 को चिह्नित करें, फिर पुनर्निर्माण के लिए एक बार संचयी योग निकालें। तेज़ अपडेट, एक बार पढ़ना। ✅