Segment Tree adalah struktur data berbasis pohon biner yang digunakan untuk menyimpan informasi tentang interval atau "segmen". Tujuan utamanya adalah untuk memproses query yang melibatkan range (misalnya, mencari jumlah elemen dalam sebuah range, nilai minimum, atau nilai maksimum) dan juga melakukan update pada elemen individual atau range dalam array underlying secara efisien. Setiap node dalam Segment Tree merepresentasikan sebuah interval, di mana node root merepresentasikan seluruh array, dan node daun merepresentasikan elemen tunggal. Node internal merepresentasikan gabungan dari interval yang diwakili oleh kedua child-nya.
Proses membangun Segment Tree dimulai dari array awal. Secara rekursif, setiap node internal menghitung nilai yang relevan (misalnya, total jumlah) dari interval yang diwakili oleh anak-anaknya. Setelah dibangun, operasi query untuk range tertentu akan "melintasi" pohon, hanya mengunjungi node yang intervalnya tumpang tindih dengan range query. Demikian pula, operasi update untuk sebuah elemen akan mengikuti jalur dari root ke node daun yang sesuai dan memperbarui nilai pada node-node di jalur tersebut, memastikan informasi di setiap node di sepanjang jalur tetap konsisten.
Kompleksitas waktu untuk operasi query dan update pada Segment Tree sangat efisien, yaitu O(log N), di mana N adalah ukuran array asli. Ini jauh lebih cepat dibandingkan dengan O(N) jika kita melakukan query secara linear pada array setiap kali. Ruang memori yang dibutuhkan untuk Segment Tree adalah O(N), karena pohon biner yang lengkap atau hampir lengkap akan memiliki sekitar 2N hingga 4N node tergantung pada implementasi dan apakah N adalah pangkat dua. Karena efisiensinya, Segment Tree menjadi pilihan populer dalam competitive programming untuk masalah yang melibatkan range query dan update.
Segment Tree adalah salah satu dari "Big 3" struktur data pohon untuk competitive programming, bersama dengan Fenwick Tree (BIT) dan Disjoint Set Union (DSU). Ia sangat fleksibel dan dapat dimodifikasi untuk mendukung berbagai jenis operasi range yang kompleks, termasuk range update dan lazy propagation.