Kupas Kode: BST Sebagai Segment Tree
Untuk setiap node, simpan banyaknya node yang ada pada subtree-nya. Saat melakukan pencarian rekursif, kita dapat menghitung indeks ke berapa node tersebut ketika BST "diratakan" menjadi sequence. Anda yang pernah menggunakan BST untuk menjawab dynamic order statistic mungkin langsung memahami apa yang baru dijelaskan. Perhatikan gambar berikut.