ਇੱਕ prefix sum ਐਰੇ ਸੰਚਿਤ ਕੁਲ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ ਤਾਂ ਜੋ ਕੋਈ ਵੀ range sum ਨੂੰ O(n) ਪ੍ਰੀ-ਪ੍ਰੋਸੈਸਿੰਗ ਤੋਂ ਬਾਅਦ O(1) ਵਿੱਚ ਜਵਾਬ ਦਿੱਤਾ ਜਾ ਸਕੇ — ਹਰੇਕ ਕਿਊਰੀ ਪ੍ਰਤੀ O(n) ਦੀ ਜਗ੍ਹਾ।
ਵਿਚਾਰ
prefix[i] ਨੂੰ ਪਹਿਲੇ i ਤੱਤਾਂ ਦਾ ਜੋੜ ਮੰਨੋ। ਫਿਰ arr[l..r] ਦਾ ਜੋੜ prefix[r+1] - prefix[l] ਹੈ।
