0Pricing
Coding Interview Prep · Pelajaran

Segment Tree: Membangun & Melakukan Query

Min, max, atau jumlah rentang dalam log n

Segment Tree: Membangun & Melakukan Query adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Melampaui Pohon Fenwick

Pohon Fenwick unggul untuk jumlah, tetapi pohon segmen menangani minimum, maksimum, FPB, dan lainnya. Pohon ini merupakan alat kerja serbaguna untuk kueri rentang.

Pohon di Atas Rentang

Setiap simpul memiliki rentang larik. Akar mencakup semuanya; anak-anaknya membagi rentang itu menjadi dua hingga daun-daunnya menyimpan elemen tunggal.

Penyimpanan Berbasis Larik

Kita menyimpan pohon dalam larik datar berukuran 2n atau 4n. Simpul 1 adalah akar; anak-anak simpul i berada pada 2i dan 2i+1.

seg = [0] * (2 * n)

Daun Menyimpan Data

Dalam bentuk iteratif, nilai asli berada di paruh kedua larik, pada indeks n hingga 2n-1.

for i in range(n):
    seg[n + i] = a[i]

Bangun dari Bawah ke Atas

Setiap simpul internal merupakan hasil combine dari kedua anaknya. Isi simpul-simpul tersebut dari n-1 turun hingga 1, dan seluruh pohon pun siap.

for i in range(n - 1, 0, -1):
    seg[i] = seg[2*i] + seg[2*i+1]

Operasi Combine

Fungsi combine menentukan cara kerja pohon. Gunakan penjumlahan untuk jumlah, min untuk nilai minimum, atau max untuk nilai maksimum. Gantilah fungsi tersebut untuk mengubah kuerinya.

def combine(x, y):
    return min(x, y)

Pembaruan Titik, Lalu Naik

Untuk mengubah satu nilai, tetapkan daun tersebut lalu berjalanlah naik ke akar sambil menghitung ulang setiap induk dari kedua anaknya.

i += n
seg[i] = value
while i > 1:
    i //= 2
    seg[i] = combine(seg[2*i], seg[2*i+1])

Mengkueri Rentang Setengah Terbuka

Kueri rentang menelusuri dari kedua ujung dan melipat simpul batas ke dalam jawaban. Intervalnya setengah terbuka, mencakup l hingga sebelum r.

Perulangan Kueri Iteratif

Gerakkan l dan r saling mendekat. Ketika suatu indeks menjadi batas ganjil, masukkan simpul tersebut ke jawaban sebelum memajukan penunjuk.

while l < r:
    if l & 1: res = combine(res, seg[l]); l += 1
    if r & 1: r -= 1; res = combine(res, seg[r])
    l //= 2; r //= 2

Logaritmik di Kedua Ujung

Pembangunan memerlukan O(n), sedangkan setiap pembaruan dan kueri memerlukan O(log n). Keseimbangan inilah yang membuat pohon segmen begitu serbaguna.

Perhatikan Elemen Identitas

Mulailah hasil Anda dengan elemen identitas operasi tersebut: 0 untuk jumlah, tak terhingga untuk minimum, dan negatif tak terhingga untuk maksimum. Awalan yang salah menghasilkan jawaban yang salah.

res = float('inf')

Pemeriksaan Singkat

Di manakah data mentah berada dalam pohon iteratif?

Rangkuman: Rentang yang Fleksibel

Anda membangun pohon segmen: daun berada di paruh kedua, induk merupakan hasil combine, serta pembaruan dan kueri O(log n) untuk jumlah, minimum, atau maksimum. 🌳

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Segment Tree: Membangun & Melakukan Query” gratis?

Ya — teks lengkap “Segment Tree: Membangun & Melakukan Query” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Segment Tree: Membangun & Melakukan Query”?

Min, max, atau jumlah rentang dalam log n Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Segment Tree: Membangun & Melakukan Query” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Fenwick Tree untuk Jumlah Awalan
  2. Inversi dengan BIT
  3. Segment Tree: Membangun & Melakukan Query
  4. Propagasi Malas untuk Pembaruan Rentang
← Kembali ke Coding Interview Prep