Segment tree

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.

Örnek çözümü göster

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]))

Kendini test et

Segment tree: kavramları eşleştir

tree[1]

16 (toplam)
tree[2]

4 (sol)
tree[3]

12 (sağ)
tree[4]

1 (yaprak)
[1, 3, 5, 7] için segment tree kökü kaç olur?
- 4
- 7
- 16
- 12
Cevabı göster

16 — Kök tüm elemanların toplamıdır: 1+3+5+7=16.

iç düğüm hesabı

tree[i] = tree[2*i] + tree[____*i+1]

Cevabı göster

tree[i] = tree[2*i] + tree[2*i+1]

Sıradaki ders: Özet - İleri veri yapıları

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler