Erotustaulukot välin päivityksiin

Prefix-summat vastasivat välikyselyihin nopeasti. Erotustaulukon avulla voitte puolestaan tehdä useita välin päivityksiä nopeasti. 🔁

Arvon lisääminen välin jokaiseen alkioon monta kertaa maksaa O(n) päivitystä kohden. Q päivityksen yhteydessä tämä kustannus kasvaa valtavaksi.

Sen sijaan että muuttaisitte jokaista solua, tallentakaa vain kohdat, joissa muutos alkaa ja päättyy. Merkitkää reunat, älkää keskiosaa.

Erotustaulukko tallentaa kunkin alkion ja sitä edeltävän alkion välisen eron. Yhden eron muokkaaminen siirtää vaikutusta koko myöhempään osuuteen.

Lisätessänne arvon v välille l–r lisätkää v indeksissä l ja vähentäkää v indeksissä r + 1. Vain kaksi muokkausta kattaa koko välin.

Indeksissä l oleva plusmerkki kytkee muutoksen päälle, ja indeksissä r + 1 oleva miinusmerkki kytkee sen jälleen pois päältä. Yhdessä ne rajaavat päivityksen yhteen väliin.

Jokainen päivitys vaatii vain kaksi taulukkoon kirjoittamista, joten q päivityksen tekeminen maksaa yhteensä O(q). Raskas työ siirtyy loppuun.

Kun kaikki merkinnät on tehty, laskekaa erotustaulukosta prefix-summa. Yksi läpikäynti palauttaa jokaisen lopullisen arvon.

Tehkää taulukosta yhden solun verran pidempi, jotta r + 1 ei koskaan ylitä sen loppua. Ylimääräinen suojapaikka estää indeksivirheet.

Käytätte päivitysten merkitsemiseen O(q) aikaa ja yhden O(n):n läpikäynnin taulukon palauttamiseen. Yhdistetty kustannus on paljon pienempi kuin naiivi O(n kertaa q).

Erotustaulukot ovat parhaimmillaan varausmäärien, tietullien ja muiden sellaisten tehtävien yhteydessä, joissa on paljon välin lisäys -operaatioita ja yksi lopullinen lukukerta.

Voitte koota välin päivitykset erotustaulukolla: merkitkää l ja r + 1 ja laskekaa sitten prefix-summa kerran taulukon palauttamiseksi. Nopeat päivitykset, yksi lukukerta. ✅