Tämän viikon tehtävissä keskeisessä roolissa on tietorakenne segmenttipuu. Saat tietoa segmenttipuusta lukemalla KKKK:n luvun 8.

Java-ohjelmoijat:

Luokasta IO.java on nyt käytössä uusi versio, joka on selvästi aiempaa nopeampi. Kun lähetät koodia CSES:ään, tämä luokka lisätään mukaan automaattisesti, eli sinun ei tarvitse lähettää sitä itse oman luokkasi yhteydessä.

Vinkit

Kaikissa tehtävissä segmenttipuu auttaa. Kisakoodarin käsikirjan lisäksi toinen hyvä esitys segmenttipuista on
http://www.cs.helsinki.fi/u/sysikask/oh2/segmenttipuu/

Katso myös segmenttipuuvisualisaatio.

Lumisade

[hint]Säilytä segmenttipuussa lumimäärien muutoksia vierekkäisten talojen välillä (Kisakoodarin käsikirja, luku 8.4). Voit myös tehdä muunnelman segmenttipuusta, joka tukee välien muuttamista ja yksittäisten arvojen kyselyä.[/hint]

Soittolista

[hint]Voit binäärihakemalla selvittää luvun d siten, että summa kappaleiden k,\ldots, k+d pituuksista on x. Summien kyselyyn voit käyttää segmenttipuuta. Tehtävään löytyy myös segmenttipuun rakennetta hyödyntävä tehokkaampi ratkaisu.[/hint]

Nakkikioski

[hint]Tee segmenttipuu taulukolle, johon laitetaan jonottajan kohdalle 1, mikäli hän on vielä jonossa, ja 0 jos hän on lähtenyt.[/hint]

Hintavertailu

[hint]Tallenna segmenttipuuhun alipuun minimin lisäksi tieto siitä, montako kertaa se esiintyy.[/hint]