Segment tree
- Algoritmalar kursu
- İleri seviye
- Ders 51/56
- 4 dk
Aralık sorguları için segment tree öğrenirsin.
Segment tree
Segment tree, bir dizinin aralıkları üzerinde sorgu (toplam, min, max) yapmayı sağlar. O(n) bellekle kurulu; sorgu O(log n) zamanda yanıtlanır.
Dizi [1, 3, 5, 7] için toplam segment tree'si kök 16, sol 4, sağ 12 olacak şekilde 7 düğümlü bir ağaçtır.
Ağaç kurulumu
Segment tree bir dizi olarak temsil edilir: tree[1] köktür, tree[2i] ve tree[2i+1] sol/sağ çocuktur. Yapraklar dizinin kendisidir.
Kurulum, yaprakları dizinin sonuna yerleştirip iç düğümleri çocuklarının toplamı olarak doldurur.
Uygulama build_segment_tree fonksiyonu
build_segment_tree(arr) yaz. tree dizisini kur: yaprakları sona koy, iç düğümleri çocukların toplamı yap. print(build_segment_tree([1, 3, 5, 7])) ile yazdır.
Başlangıç kodu
def build_segment_tree(arr):
# Segment tree kurÖrnek çözüm
def build_segment_tree(arr):
# Segment tree kur
n = len(arr)
tree = [0] * (2 * n)
for i in range(n):
tree[n + i] = arr[i]
for i in range(n - 1, 0, -1):
tree[i] = tree[2 * i] + tree[2 * i + 1]
return tree
print(build_segment_tree([1, 3, 5, 7]))Beklenen çıktı
[0, 16, 4, 12, 1, 3, 5, 7]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Segment tree: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
tree[1] |
16 (toplam) |
tree[2] |
4 (sol) |
tree[3] |
12 (sağ) |
tree[4] |
1 (yaprak) |
2 [1, 3, 5, 7] için segment tree kökü kaç olur?
- 4
- 7
- 16 Doğru cevap
- 12
Açıklama: Kök tüm elemanların toplamıdır: 1+3+5+7=16.
3 iç düğüm hesabı
tree[i] = tree[2*i] + tree[____*i+1]tree[i] = tree[2*i] + tree[2*i+1]Açıklama: 2 doğru.