siġar ta' segmenti u siġar ta' Fenwick (Binary Indexed Tree, BIT) it-tnejn jirrispondu għal mistoqsija ta' firxa (eż. somma fuq [l, r]) u aġġornamenti tal-punt f' O(log n), kompara ma' O(n) għal skanar ħelu jew O(n) aġġornamenti għal firxa ta' somma prefissa.
Array + many "sum of range [l,r]" and "update index i" calls:
naive prefix sums: query O(1) but UPDATE is O(n)
segment/Fenwick: query O(log n) AND update O(log n)
class Fenwick:
def __init__(self, n):
self.t = [0]*(n+1)
def update(self, i, delta): # O(log n)
i += 1
while i < len(self.t):
self.t[i] += delta
i += i & (-i) # jump to next responsible node
def prefix(self, i): # sum of [0..i], O(log n)
i += 1; s = 0
while i > 0:
s += self.t[i]
i -= i & (-i)
return s
def range_sum(self, l, r):
return self.prefix(r) - self.prefix(l-1)
Siġar ta' segmenti taħżen aggregat għal kull segmenti tal-firxa f'siġar binarja, u tappoġġa xi operazzjoni assoċjattiva (somma, min, max, gcd) u, b'propagazzjoni faċċa, aġġornamenti ta' firxa wkoll.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Siġar ta' segmenti | |
|---|---|---|
| Mistoqsija / aġġornament | O(log n) | O(log n) |
| Spazju | O(n) | O(2n) |
| Operazzjonijiet | somom (invertibili) | xi operazzjoni assoċjattiva |
| Aġġornamenti ta' firxa | aktar diffiċili | faċli (propagazzjoni faċċa) |
| Daqs tal-kod | ħafna żgħir | akbar |
Il-laboratorji haw jaslu "aġġorna valur, imbagħad mistoqsija aggregat fuq firxa" mhux rqiqa — essenzjali għall-programmazz kompetittiv, twiebanċ ta' analitiċi, u problemi tal-intervall.
Il-għażla bejn it-tnejn hija trade-off: siġar ta' Fenwick huwa żgħir u mhux rqiq għal somom, filwaqt li siġar ta' segmenti huwa aktar flessibli għal carjki ta' xogħol min/max/aġġornament ta' firxa.
Librerija ta' mistoqsijiet ta' intervisti tal-IT b'tweġibiet dettaljati — minn Junior sa Senior.
Iddona