Eli miten voisi koodata täällä viimeisenä esitellyn segmenttipuun (tuota sitten kutsutaan yleisesti sisupuuksi 8)) kaksiuloitteisena niin, että tukisi alueille lisäämistä ja alueiden minimin kyselyä. Kelpaa kyllä myös "laiskuutta" käyttävä 2d-minimisegmenttipuu, jos se on edes mahdollinen :P
En jaksanut lukea tarkasti, mutta selitäpä ensin, millaisia ongelmia syntyy, jos jokaisella solmulla olisi kahden sijaan neljä alipuuta neliön muodossa.
Jos tarkoitat quadtreetä, ongelmana on se, että operaatiot ovat käsittääkseni pahimmillaan lineaarisia (esim. kyselyt alueelta 1*k). Haluaisin jonkun O((log n)^2)-aikavaativuuden
Toimiiko wikipedian ehdottama Punamusta puu ongelmassasi?
http://fi.wikipedia.org/wiki/Punamusta_puu
Tosin en jaksanut lukea kovinkaan tarkkaan wikipedian sivua.
Ahaa, eli kysymyksesi ei olekaan, miten sen voi koodata, vaan haluat tietää, onko siihen jokin tehokkaampi ratkaisu.
Vertailusi on minusta omituinen. Ethän voi mitenkään odottaa, että n luvun lista ja n² luvun neliö olisivat verrannolliset, vaan on loogista katsoa lukujen kokonaismäärää. Näin ajateltuna vaikein operaatio on nähdäkseni ”vain” luokkaa log(sqrt(n))*sqrt(n), missä n on lukujen kokonaismäärä ja sqrt(n) on neliön sivun pituus.
Hauskasti samaan tulokseen pääsee myös sillä, että tekee neliön jokaiselle riville oman segmenttipuun ja käy vain silmukalla läpi pyydettyjen rivien segmenttipuut.
Arvelen, että yleisessä tapauksessa tehokkaampaa ratkaisua ei ole, mutta ehkä kannattaa odottaa vielä jonkun algoritmigurun sanaa.
Sanoin huonosti tuon vertailun. Tarkoitin siis tuolla n:llä neliön sivun pituutta.
Lisäys: Ajattelin, että mainitessani segmenttipuun, olisi ollut selvää, että haluan jonkun logaritmisen aikaaativuuden 8) Punamusta puu on aivan erilaisiin asioihin soveltuva tietorakenne...
Lisäys: Niin ja selvennettäköön vielä sen verran, että osaan kyllä koodata alueille lisäämisiä ja alueiden summien kyselyjä tukevan 2d-sisupuun.
Aihe on jo aika vanha, joten et voi enää vastata siihen.