एक prefix sum array ले संचयी योगफलहरू भण्डार गर्छ ताकि कुनै पनि range sum लाई O(n) पूर्वप्रसंस्करण पछि O(1) मा उत्तर दिन सकिन्छ — प्रत्येक क्वेरीमा O(n) को सट्टा।
अवधारणा
लाई पहिलो तत्वहरूको योगफल मान्नुहोस्। त्यसपछि को योगफल हो।
एक prefix sum array ले संचयी योगफलहरू भण्डार गर्छ ताकि कुनै पनि range sum लाई 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
स्थिर डेटामा धेरै range-sum क्वेरीहरूको लागि आदर्श। भेरिएन्टहरू: submatrix सुमहरूको लागि 2D prefix sums, prefix XOR, र range अपडेटहरूको लागि difference arrays। यदि array अक्सर परिवर्तन हुन्छ भने, यसको सट्टा Fenwick/segment tree प्रयोग गर्नुहोस्। अनुक्रमणिका अफसेट (आकार n+1) को ध्यान राख्नुहोस्।
Prefix sums ले दोहोरिने O(n) range क्वेरीहरूलाई O(1) लुकअपहरूमा रूपान्तरित गर्दछ — जब क्वेरीहरू बारम्बार हुन्छन् तब ठूलो जीत।
एक पटक पूर्वकम्प्यूट गर्ने, द्रुत उत्तर दिने प्याटर्न धेरै डेटा-प्रसंस्करण कार्यहरूमा सामान्यीकरण गर्दछ।
यो प्रतियोगी प्रोग्रामिङको एक प्रमुख तत्व र विश्लेषणमा एक सामान्य बिल्डिङ ब्लक हो।