एक उपसर्ग योग सरणी संचयी कुल संग्रहीत करती है ताकि कोई भी सीमा योग O(n) पूर्वप्रसंस्करण के बाद O(1) में उत्तर दिया जा सके — प्रति प्रश्न O(n) के बजाय।
विचार
prefix[i] पहले i तत्वों का योग हो। फिर arr[l..r] का योग prefix[r+1] - prefix[l] है।
एक उपसर्ग योग सरणी संचयी कुल संग्रहीत करती है ताकि कोई भी सीमा योग O(n) पूर्वप्रसंस्करण के बाद O(1) में उत्तर दिया जा सके — प्रति प्रश्न O(n) के बजाय।
prefix[i] पहले i तत्वों का योग हो। फिर arr[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) खोजों में बदलते हैं — जब प्रश्न बार-बार आएं तो विशाल लाभ।
एक बार पूर्वकलन करें, तेजी से उत्तर दें पैटर्न कई डेटा-प्रोसेसिंग कार्यों को सामान्यीकृत करता है।
यह प्रतिस्पर्धी प्रोग्रामिंग का एक मुख्य आधार है और विश्लेषण में एक सामान्य निर्माण ब्लॉक है।