ਇੱਕ prefix sum ਐਰੇ ਸੰਚਿਤ ਕੁਲ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ ਤਾਂ ਜੋ ਕੋਈ ਵੀ range sum ਨੂੰ 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
ਸਟੈਟਿਕ ਡਾਟਾ ਤੇ ਬਹੁਤ ਸਾਰੀਆਂ range-sum ਕਿਊਰੀਜ ਲਈ ਨਿਮਖ ਵਰਤਾਓ। ਸੰਸਕਰਨ: submatrix ਜੋੜਾਂ ਲਈ 2D prefix sums, prefix XOR, ਅਤੇ range ਅਪਡੇਟਸ ਲਈ difference arrays। ਜੇ ਐਰੇ ਅਕਸਰ ਬਦਲਦਾ ਹੈ, ਇਸਦੀ ਜਗ੍ਹਾ Fenwick/segment tree ਵਰਤੋ। ਇੰਡੈਕਸ ਔਫਸੈਟ (ਆਕਾਰ n+1) ਦਾ ਧਿਆਨ ਰੱਖੋ।
Prefix sums ਨੂੰ ਦੁਹਰਾਇਆ ਗਿਆ O(n) range ਕਿਊਰੀਜ ਨੂੰ O(1) ਲੁਕਅਪ ਵਿੱਚ ਬਦਲ ਦਿੰਦਾ ਹੈ — ਜਦੋਂ ਕਿਊਰੀਜ ਵਾਰ-ਵਾਰ ਹੁੰਦੀਆਂ ਹਨ ਤਾਂ ਵੱਡੀ ਜਿੱਤ।
ਇੱਕ ਵਾਰ ਪ੍ਰੀ-ਕੈਲਕੁਲੇਟ ਕਰੋ, ਤੇਜ਼ ਜਵਾਬ ਦਿਓ ਪੈਟਰਨ ਬਹੁਤ ਸਾਰੇ ਡਾਟਾ-ਪ੍ਰੋਸੈਸਿੰਗ ਕੰਮਾਂ ਨੂੰ ਜਨਰੂਪ ਕਰਦਾ ਹੈ।
ਇਹ ਪ੍ਰਤੀਯੋਗਿਤਾ ਪ੍ਰੋਗ੍ਰਾਮਿੰਗ ਦਾ ਇੱਕ ਮੁੱਖ ਅੰਗ ਹੈ ਅਤੇ ਵਿਸ਼ਲੇਸ਼ਣ ਵਿੱਚ ਇੱਕ ਆਮ ਇਕਾਈ ਹੈ।