घटाव से किसी भी Range का Sum

प्रिफिक्स ऐरे बनाना केवल तैयारी थी। अब असली जादू आता है: किसी भी सीमा-योग का उत्तर केवल एक घटाव से देना। ⚡

सीमा-योग केवल एक बड़े कुल योग में से छोटे कुल योग को घटाना है। दो प्रिफिक्स मानों को घटाने पर सीमा के बाहर के सभी तत्व साफ़ तौर पर रद्द हो जाते हैं।

l से r तक के तत्वों का योग निकालने के लिए prefix[r + 1] में से prefix[l] घटाइए। यह एकल सूत्र हर परास के लिए काम करता है।

prefix[r + 1] में r तक के सभी तत्व होते हैं, और prefix[l] में l से पहले तक के तत्व होते हैं। अंतर निकालने पर ठीक बीच वाला भाग बचता है।

[3, 1, 4] के लिए संचयी योग [0, 3, 4, 8] है। सूचकांक 1 से 2 तक का योग निकालने के लिए 8 में से 3 घटाइए, जिससे 5 मिलता है। यह 1 और 4 के योग के बराबर है।

हर प्रश्न में केवल एक घटाव करना होता है, इसलिए उसका समय O(1) है। एक हज़ार प्रश्नों में प्रति प्रश्न उतना ही समय लगेगा जितना एक प्रश्न में।

सबसे आम चूक ऊपरी सीमा के सूचकांक में होती है। शुरुआत में शून्य होने पर हमेशा prefix[r + 1] का उपयोग करें, prefix[r] का नहीं। इस सीमा को सही रखें।

पहले ही तय कर लें कि r को शामिल करना है या नहीं। यह सूत्र l और r दोनों को समावेशी मानता है, जैसा कि अधिकांश प्रतियोगिता-प्रश्नों में अपेक्षित होता है।

एक छोटा सहायक फ़ंक्शन आपके तर्क को पढ़ने योग्य और आपके सूचकांकों को एक ही स्थान पर रखता है। गणना को सीधे लिखने के बजाय इस सहायक का उपयोग करें।

पूरी सारणी का योग निकालने के लिए l को 0 और r को n - 1 रखें। सूत्र prefix[n], यानी कुल योग, देता है।

जब किसी स्थिर सारणी पर बहुत से परास-योग प्रश्न पूछे जाएँ, तब संचयी योग हर प्रश्न के लिए O(n) का लूप चलाने के बजाय तुरंत उत्तर देता है।

अब आप prefix[r + 1] में से prefix[l] घटाकर किसी भी परास का योग O(1) समय में निकाल सकते हैं। शुरुआत के शून्य से मिलने वाले विस्थापन का ध्यान रखें और त्रुटियों से मुक्त रहें। ✅