Kali ini saya akan berbagi suatu teknik yang lucu, yaitu mengoprek "jeroan"
segment tree dan BIT. Kadang-kadang, dengan mengetahui struktur dalam suatu objek dan langsung memanipulasinya, kita bisa melakukan berbagai hal dengan lebih efisien. Misalnya kalau Anda paham struktur dalam televisi, mungkin Anda bisa mengatur supaya televisinya otomatis mati pada jam-jam tertentu.
Saya akan memberikan beberapa contoh yang umum.
Contoh umum
Misalkan diberikan soal:
Terdapat sebuah array A yang awalnya kosong dan N operasi, yang bisa berupa:
- tambah x, artinya tambahkan x ke dalam array A. Dijamin tidak nilai-nilai di dalam array A akan selalu unik
- tanya k, artinya cetak bilangan terkecil ke-k di dalam array A pada saat itu
Batasan:
- 1 ≤ N ≤ 100.000
- Pada setiap operasi tambah, 1 ≤ x ≤ N
- Pada setiap operasi tanya, 1 ≤ k ≤ N
Salah satu cara yang mungkin langsung terpikir adalah dengan BST. Namun BST relatif sulit untuk di-coding, lagipula tidak ada operasi menghapus. Oleh karena itu, marilah kita coba kerjakan dengan
segment tree.