एक उपसर्ग योग सरणी संचयी कुल संग्रहीत करती है ताकि कोई भी सीमा योग O(n) पूर्वप्रसंस्करण के बाद O(1) में उत्तर दिया जा सके — प्रति प्रश्न O(n) के बजाय।
विचार
पहले तत्वों का योग हो। फिर का योग है।
एक उपसर्ग योग सरणी संचयी कुल संग्रहीत करती है ताकि कोई भी सीमा योग O(n) पूर्वप्रसंस्करण के बाद O(1) में उत्तर दिया जा सके — प्रति प्रश्न O(n) के बजाय।
पहले तत्वों का योग हो। फिर का योग है।
prefix[i]iarr[l..r]prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, l, r): # inclusive l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
स्थिर डेटा पर कई सीमा-योग प्रश्नों के लिए आदर्श। संस्करण: सबमैट्रिक्स योग के लिए 2D उपसर्ग योग, उपसर्ग XOR, और सीमा अपडेट के लिए अंतर सरणी। यदि सरणी बार-बार बदलती है, तो इसके बजाय एक Fenwick/segment tree का उपयोग करें। सूचकांक ऑफसेट देखें (आकार n+1)।
उपसर्ग योग दोहराए गए O(n) सीमा प्रश्नों को O(1) खोजों में बदलते हैं — जब प्रश्न बार-बार आएं तो विशाल लाभ।
एक बार पूर्वकलन करें, तेजी से उत्तर दें पैटर्न कई डेटा-प्रोसेसिंग कार्यों को सामान्यीकृत करता है।
यह प्रतिस्पर्धी प्रोग्रामिंग का एक मुख्य आधार है और विश्लेषण में एक सामान्य निर्माण ब्लॉक है।
विस्तृत उत्तरों के साथ IT इंटरव्यू प्रश्नों की एक लाइब्रेरी — जूनियर से सीनियर तक।
दान करें