Etuliitteen summa -taulukko säilyttää kumulatiiviset summat, joten mikä tahansa alueen summa voidaan vastata O(1) -ajassa O(n) -esikäsittelyn jälkeen — O(n):n sijaan per kysymys.
Idea
Olkoon ensimmäisen elementin summa. Tällöin :n summa on .
Etuliitteen summa -taulukko säilyttää kumulatiiviset summat, joten mikä tahansa alueen summa voidaan vastata O(1) -ajassa O(n) -esikäsittelyn jälkeen — O(n):n sijaan per kysymys.
Olkoon ensimmäisen elementin summa. Tällöin :n summa on .
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
Ihanteellinen monille alueen summa -kysymyksille staattisilla tiedoilla. Muunnelmat: 2D etuliitteen summat alimatriisin summille, etuliitteen XOR ja eroavaisuustaulukot aluepäivityksille. Jos taulukko muuttuu usein, käytä sen sijaan Fenwick/segment-puuta. Huomio indeksin siirtymä (koko n+1).
Etuliitteen summat muuntavat toistuvia O(n) aluekysymyksiä O(1) -hakuiksi — valtava voitto, kun kysymykset ovat usein toistuvia.
Esikäsittele kerran, vastaa nopeasti -malli yleistyy moniin tietojen käsittelytehtäviin.
Se on kilpailuohjelmoinnin kulmakivi ja yleinen rakennuspalikka analyytiikassa.
Kirjasto IT-haastattelukysymyksiä yksityiskohtaisine vastauksineen — Juniorista Senioriin.
Lahjoita