Fenwick-träd för prefixsummor
Punktuppdatering och prefixfråga i log n
Fenwick-träd för prefixsummor är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Varför prefixarrayer inte räcker
En vanlig prefixsumme-array besvarar intervallfrågor direkt, men en enda uppdatering tvingar er att bygga om den. Med många uppdateringar blir det långsamt. ⏱️
Fenwickträdet gör entré
Fenwickträdet, eller BIT, stöder både punktuppdateringar och prefixfrågor på O(log n). Det är ert förstahandsval för dynamiska löpande summor.
Indexerad från ett från början
Ett Fenwickträd använder en array som är indexerad från 1. Vi använder index 0 som en tom platshållare, så alla riktiga data börjar på position 1.
tree = [0] * (n + 1)Magin med den lägsta satta biten
Varje index täcker ett block av värden. Blockstorleken är i & -i, alltså den lägsta satta biten i i. Det här enda tricket driver hela trädet.
lowbit = i & -iUppdatera en enskild position
För att lägga till ett värde på position i hoppar ni framåt med lowbit i varje steg och berör varje block som innehåller i.
while i <= n:
tree[i] += delta
i += i & -iBeräkna en prefixsumma
För att summera de första i värdena går ni bakåt och subtraherar lowbit i varje steg tills ni når noll.
s = 0
while i > 0:
s += tree[i]
i -= i & -iBåda looparna är logaritmiska
Varje loop släcker en bit per iteration, så den körs högst log n gånger. Därför förblir både uppdateringar och frågor snabba.
Intervallsumma från två prefix
Vill ni ha summan från l till r? Ta prefix(r) minus prefix(l-1), precis som med en statisk prefix-array, men nu är även uppdateringar billiga.
range_sum = query(r) - query(l - 1)Bygg trädet
Den enklaste konstruktionen anropar bara update för varje startvärde. Det ger O(n log n) och är tillräckligt snabbt i de flesta tävlingar.
for i, v in enumerate(a, 1):
update(i, v)Ett mycket litet minnesavtryck
Ett Fenwickträd behöver bara en array av storlek n+1. Det kompakta minnesavtrycket är en del av förklaringen till att det är så uppskattat i tävlingar. 💾
När BIT passar
Välj ett Fenwickträd när ni blandar punktuppdateringar med prefix- eller intervallsummor. Det är kort att koda och svårt att slå.
Snabb kontroll
Låt oss befästa hur looparna förflyttar sig.
Sammanfattning: BIT-grunder
Ni har mött Fenwickträdet: indexerat från 1, drivet av i & -i, med både punktuppdatering och prefixfråga på O(log n). Härnäst använder vi det för att räkna inversioner. 🎯
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Fenwick-träd för prefixsummor” gratis?
Ja – hela texten till ”Fenwick-träd för prefixsummor” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Fenwick-träd för prefixsummor”?
Punktuppdatering och prefixfråga i log n Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Fenwick-träd för prefixsummor”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Fenwick-träd för prefixsummor
- Inversioner med ett BIT
- Segmentträd: bygg och fråga
- Lat propagation för intervalluppdateringar