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