2008/6/7 Hendry <[EMAIL PROTECTED]>: > Kalau membaca soal berikut, asumsi saya, array of integer A tersebut > adalah selalu data yang baru, dan kita diminta mencari bilangan > integer terkecil. Kalau permintaan nya membuat algoritma ataupun > function yang selalu ready menerima data baru, mem preprocess data, > lalu the next step selalu menggunakan data yang sudah di preprocess, > bukankah itu sudah mem bypass satu step algoritma dari soal tersebut? > CMIIW
Array A itu fixed dengan jumlah element N. Saya mempunyai banyak queries: cari bilangan terkecil antara index i dan index j (inclusive). Jadi meskipun array A itu acak, tapi array A tidak pernah berubah. Dan array A yang sama ini akan di query terus menerus. Otomatis kita harus buat query ini efisien donk? Nah, algo linearnya kan itu scan dari i ke j, cari yang minimum, lalu print. Tapi algo itu O ( N ) jalannya. Pertanyaanya, bisakah kita "preprocess" array A ini sedemikian sehingga setiap query [i, j] bisa diprocess hanya dengan O ( log N ). Tetapi one-time preprocessnya tidak boleh lebih dari O ( N log N ). Felix Halim
