Viikon 6 aiheena on välikyselyt, erityisesti segmenttipuut. KKKK luvut 9 ja 28 käsittelevät segmenttipuita. Luvun 9 asiat pitäisivät riittää ensimmäisen viiden tehtävän ratkaisuun. Kuudennessa tehtävässä tarvitaan luvun 28 laiskaa segmenttipuuta.

Katso myös segmenttipuuvisualisaatio.

Alla on vihjeitä tehtäviin. Kannattaa kuitenkin ensin miettiä ilman vihjettä. Vihjeen näet maalaamalla sen hiirellä.

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]

Muutos

[hint]Tallenna jokaiseen segmenttipuun solmuun välin minimi, maksimi ja suurin muutos.[/hint]

Tietorakenne

[hint]Käytä laiskaa segmenttipuuta. Tallenna välille kaksi laiskaa arvoa: arvo joksi väli on asetettu ja välille lisätty arvo.[/hint]