Algoritmalar
tr

Segment Ağacı

Ağaçlar O(log n) query O(n)

Dizi aralıkları üzerinde bir ikili ağaç: her düğüm bir toplam saklar, böylece aralık sorguları O(log n) kapsayıcı düğümü birleştirerek O(log n)'de çözülür.

37[0,7]12[0,3]7[0,1]2[0]5[1]5[2,3]1[2]4[3]25[4,7]12[4,5]9[4]3[5]13[6,7]7[6]6[7]
input array
20
51
12
43
94
35
76
67
1/24

Yaprak [0] = 2.

DeğişmezHer düğüm kendi aralığının toplamını tutar, bu yüzden her sorgu tarama değil birkaç tam aralıktır.

segment-tree.c
int tree[4 * MAXN];
 
void build(int a[], int node, int lo, int hi) {
    if (lo == hi) {
        tree[node] = a[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    build(a, 2*node, lo, mid);
    build(a, 2*node+1, mid+1, hi);
    tree[node] = tree[2*node] + tree[2*node+1];
}
 
int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return tree[node];
    int mid = (lo + hi) / 2;
    return query(2*node, lo, mid, l, r)
         + query(2*node+1, mid+1, hi, l, r);
}

Segment Ağacı nasıl çalışır?

Her düğüm bir dizi aralığının özetini tutar; çocuklar aralığı ikiye böler. Sorgu yanıtını O(log n) ayrık kapsayıcı düğümden diker; güncelleme tek yaprak-kök yolunu tazeler.

Ne zaman kullanılır?

Nokta güncellemeleriyle iç içe aralık sorguları (toplam/min/maks): yarışma programlama, analitik pencereler.