Array prefix sum jaħżen somom kummulativi sabiex kwalunkwe range sum jista' jiġi miegħed f'O(1) wara l-preprocessing O(n) — minflok O(n) kull query.
L-idea
Halli prefix[i] tkun is-suma tal-ewwel i elementi. Allura s-suma ta' arr[l..r] hija .
Array prefix sum jaħżen somom kummulativi sabiex kwalunkwe range sum jista' jiġi miegħed f'O(1) wara l-preprocessing O(n) — minflok O(n) kull query.
Halli prefix[i] tkun is-suma tal-ewwel i elementi. Allura s-suma ta' arr[l..r] hija .
Librerija ta' mistoqsijiet ta' intervisti tal-IT b'tweġibiet dettaljati — minn Junior sa Senior.
Iddonaprefix[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
Ideali għal ħafna range-sum queries fuq data statika. Varjanti: prefix sums 2D għal submatrix sums, prefix XOR, u difference arrays għal range updates. Jekk l-array jinbidel spiss, uża Fenwick/segment tree minflok. Agħti attenzjoni għall-offset ta' l-indiċi (daqs n+1).
Il-prefix sums jibdlu r-repeated O(n) range queries f'O(1) lookups — rebbieħa kbira meta queries huma frewenti.
Il-precompute-darba, meet-harġa pattern jiġeneralizza għal bosta data-processing tasks.
Hu element fundamentali ta' competitive programming u common building block fl-analytics.