AlgoPit

Segment Tree (Aralık Ağacı) Veri Yapısı

Segment Tree, bir dizi üzerinde aralık sorguları (range queries) ve nokta güncellemeleri yapabilmek için tasarlanmış binary tree tabanlı bir veri yapısıdır. Toplam, minimum, maksimum gibi işlemleri logaritmik zamanda gerçekleştirir.

Avantajlar

  • Aralık sorguları çok hızlıdır (O(log n))
  • Nokta güncellemeleri etkilidir (O(log n))
  • Lazy propagation ile aralık güncellemeleri destekler
  • Çeşitli associative operations için kullanılabilir
  • Online algorithm - önceden tüm sorguları bilmek gerekmez

Dezavantajlar

  • Implementation karmaşıklığı yüksektir
  • Sabit boyutlu diziler için ekstra bellek kullanır
  • Cache performance bazı durumlarda kötü olabilir
  • Küçük diziler için overhead fazla olabilir

İnteraktif Segment Tree Görselleştirme

Aşağıdaki görselleştirici ile Segment Tree veri yapısını keşfedebilirsiniz. Dizi elemanlarını değiştirin, aralık sorguları yapın ve tree'nin nasıl güncellendiğini gözlemleyin.

Segment Tree Düğüm Renkleri

Yaprak düğümü (tek eleman)
İç düğüm (aralık)

Genel Bilgiler

• Her düğüm bir aralığı ve o aralıktaki toplam/min/max değerleri içerir

• Yaprak düğümler orijinal dizi elemanlarını temsil eder

• İç düğümler alt aralıkların birleşimini temsil eder

Trie (Prefix Tree)

Zaman Karmaşıklığı:

  • Ekleme: O(m) - m kelime uzunluğu
  • Arama: O(m)
  • Prefix arama: O(p + k) - p prefix uzunluğu, k sonuç sayısı

Alan Karmaşıklığı: O(ALPHABET_SIZE * N * M)

Kullanım Alanları: Otomatik tamamlama, yazım kontrolü, IP routing

Segment Tree

Zaman Karmaşıklığı:

  • İnşa etme: O(n)
  • Aralık sorgusu: O(log n)
  • Güncelleme: O(log n)

Alan Karmaşıklığı: O(n)

Kullanım Alanları: Aralık toplamı, min/max sorguları, lazy propagation

Aralık Sorgusu Demo

Dizi, başlangıç indeks ve bitiş indeks girerek aralık sorgusu yapın

Sonuç yok

Nokta Güncelleme Demo

Belirli bir indeksteki değeri güncelleyin

Sonuç yok

JavaScript Implementasyonu

Segment Tree veri yapısının tam JavaScript implementasyonu. Aralık sorguları, nokta güncellemeleri ve tree validasyonu özellikleri içerir.

Segment Tree - Tam Implementasyon
1// Segment Tree JavaScript implementasyonu
2class SegmentTreeNode {
3  constructor(start, end, sum = 0, min = Infinity, max = -Infinity) {
4    // Bu düğümün kapsadığı aralığın başlangıç ve bitiş indeksleri
5    this.start = start;
6    this.end = end;
7    
8    // Aralıktaki değerlerin toplamı, minimumu ve maksimumu
9    this.sum = sum;
10    this.min = min;
11    this.max = max;
12    
13    // Sol ve sağ çocuk düğümler
14    this.left = null;
15    this.right = null;
16    
17    // Lazy propagation için (opsiyonel)
18    this.lazyValue = 0;
19    this.hasLazyValue = false;
20  }
21}
22
23class SegmentTree {
24  constructor(array) {
25    // Orijinal diziyi kopyala
26    this.originalArray = [...array];
27    
28    // Segment tree'yi build et
29    this.root = array.length > 0 ? this.buildTree(array, 0, array.length - 1) : null;
30  }
31
32  // Segment tree'yi recursive olarak build etme
33  buildTree(array, start, end) {
34    // Base case: yaprak düğüm (tek eleman)
35    if (start === end) {
36      return new SegmentTreeNode(
37        start, 
38        end, 
39        array[start], 
40        array[start], 
41        array[start]
42      );
43    }
44
45    // Recursive case: iç düğüm
46    const mid = Math.floor((start + end) / 2);
47    const leftChild = this.buildTree(array, start, mid);
48    const rightChild = this.buildTree(array, mid + 1, end);
49
50    // Parent düğümün değerlerini çocuklardan hesapla
51    const node = new SegmentTreeNode(start, end);
52    node.left = leftChild;
53    node.right = rightChild;
54    
55    // Aggregation operations
56    node.sum = leftChild.sum + rightChild.sum;
57    node.min = Math.min(leftChild.min, rightChild.min);
58    node.max = Math.max(leftChild.max, rightChild.max);
59
60    return node;
61  }
62
63  // Aralık toplamı sorgusu - O(log n)
64  querySum(queryStart, queryEnd) {
65    if (!this.root || queryStart > queryEnd) return 0;
66    return this.querySumHelper(this.root, queryStart, queryEnd);
67  }
68
69  // Aralık minimum sorgusu - O(log n)
70  queryMin(queryStart, queryEnd) {
71    if (!this.root || queryStart > queryEnd) return Infinity;
72    return this.queryMinHelper(this.root, queryStart, queryEnd);
73  }
74
75  // Aralık maksimum sorgusu - O(log n)
76  queryMax(queryStart, queryEnd) {
77    if (!this.root || queryStart > queryEnd) return -Infinity;
78    return this.queryMaxHelper(this.root, queryStart, queryEnd);
79  }
80
81  // Nokta güncelleme - O(log n)
82  updatePoint(index, newValue) {
83    if (!this.root || index < 0 || index >= this.originalArray.length) return;
84    
85    this.originalArray[index] = newValue;
86    this.updatePointHelper(this.root, index, newValue);
87  }
88
89  // Aralık güncelleme - lazy propagation ile O(log n)
90  updateRange(updateStart, updateEnd, delta) {
91    if (!this.root || updateStart > updateEnd) return;
92    
93    // Basit implementasyon: tüm noktaları tek tek güncelle
94    for (let i = updateStart; i <= updateEnd; i++) {
95      if (i >= 0 && i < this.originalArray.length) {
96        this.originalArray[i] += delta;
97      }
98    }
99    
100    // Tree'yi yeniden build et (gerçek implementasyonda lazy propagation kullanılır)
101    this.root = this.buildTree(this.originalArray, 0, this.originalArray.length - 1);
102  }
103
104  // Sum query helper - recursive implementation
105  querySumHelper(node, queryStart, queryEnd) {
106    // Tam kapsama - node'un tüm aralığı sorgu aralığında
107    if (queryStart <= node.start && queryEnd >= node.end) {
108      return node.sum;
109    }
110
111    // Kapsama yok - sorgu aralığı ile node aralığı kesişmiyor
112    if (queryEnd < node.start || queryStart > node.end) {
113      return 0;
114    }
115
116    // Kısmi kapsama - sol ve sağ çocukları sorgula
117    let result = 0;
118    if (node.left) {
119      result += this.querySumHelper(node.left, queryStart, queryEnd);
120    }
121    if (node.right) {
122      result += this.querySumHelper(node.right, queryStart, queryEnd);
123    }
124
125    return result;
126  }
127
128  // Min query helper - recursive implementation
129  queryMinHelper(node, queryStart, queryEnd) {
130    // Tam kapsama
131    if (queryStart <= node.start && queryEnd >= node.end) {
132      return node.min;
133    }
134
135    // Kapsama yok
136    if (queryEnd < node.start || queryStart > node.end) {
137      return Infinity;
138    }
139
140    // Kısmi kapsama
141    let leftMin = Infinity;
142    let rightMin = Infinity;
143
144    if (node.left) {
145      leftMin = this.queryMinHelper(node.left, queryStart, queryEnd);
146    }
147    if (node.right) {
148      rightMin = this.queryMinHelper(node.right, queryStart, queryEnd);
149    }
150
151    return Math.min(leftMin, rightMin);
152  }
153
154  // Max query helper - recursive implementation
155  queryMaxHelper(node, queryStart, queryEnd) {
156    // Tam kapsama
157    if (queryStart <= node.start && queryEnd >= node.end) {
158      return node.max;
159    }
160
161    // Kapsama yok
162    if (queryEnd < node.start || queryStart > node.end) {
163      return -Infinity;
164    }
165
166    // Kısmi kapsama
167    let leftMax = -Infinity;
168    let rightMax = -Infinity;
169
170    if (node.left) {
171      leftMax = this.queryMaxHelper(node.left, queryStart, queryEnd);
172    }
173    if (node.right) {
174      rightMax = this.queryMaxHelper(node.right, queryStart, queryEnd);
175    }
176
177    return Math.max(leftMax, rightMax);
178  }
179
180  // Point update helper - recursive implementation
181  updatePointHelper(node, index, newValue) {
182    // Base case: yaprak düğüm
183    if (node.start === node.end) {
184      node.sum = newValue;
185      node.min = newValue;
186      node.max = newValue;
187      return;
188    }
189
190    // Recursive case: uygun çocuğu güncelle
191    const mid = Math.floor((node.start + node.end) / 2);
192    if (index <= mid && node.left) {
193      this.updatePointHelper(node.left, index, newValue);
194    } else if (node.right) {
195      this.updatePointHelper(node.right, index, newValue);
196    }
197
198    // Parent node değerlerini güncelle
199    if (node.left && node.right) {
200      node.sum = node.left.sum + node.right.sum;
201      node.min = Math.min(node.left.min, node.right.min);
202      node.max = Math.max(node.left.max, node.right.max);
203    }
204  }
205
206  // Tree structure'ı döndürme (görselleştirme için)
207  getTreeStructure() {
208    return this.root;
209  }
210
211  // Tree yüksekliğini hesaplama
212  getHeight() {
213    return this.getHeightHelper(this.root);
214  }
215
216  // Height helper - recursive implementation
217  getHeightHelper(node) {
218    if (!node) return 0;
219
220    const leftHeight = this.getHeightHelper(node.left);
221    const rightHeight = this.getHeightHelper(node.right);
222
223    return 1 + Math.max(leftHeight, rightHeight);
224  }
225
226  // Orijinal diziyi döndürme
227  getArray() {
228    return [...this.originalArray];
229  }
230
231  // Tree istatistiklerini döndürme
232  getStatistics() {
233    let nodeCount = 0;
234    let leafCount = 0;
235
236    const traverse = (node) => {
237      if (!node) return;
238      
239      nodeCount++;
240      if (node.start === node.end) {
241        leafCount++;
242      }
243
244      traverse(node.left);
245      traverse(node.right);
246    };
247
248    traverse(this.root);
249
250    return {
251      nodeCount,
252      leafCount,
253      height: this.getHeight(),
254      arraySize: this.originalArray.length
255    };
256  }
257
258  // Tree'nin geçerli olup olmadığını kontrol etme
259  validateTree() {
260    if (!this.root) return true;
261
262    const validate = (node) => {
263      if (!node) return true;
264
265      // Yaprak düğüm kontrolü
266      if (node.start === node.end) {
267        const expectedValue = this.originalArray[node.start];
268        return node.sum === expectedValue && 
269               node.min === expectedValue && 
270               node.max === expectedValue;
271      }
272
273      // İç düğüm kontrolü
274      if (!node.left || !node.right) return false;
275
276      const expectedSum = node.left.sum + node.right.sum;
277      const expectedMin = Math.min(node.left.min, node.right.min);
278      const expectedMax = Math.max(node.left.max, node.right.max);
279
280      return node.sum === expectedSum &&
281             node.min === expectedMin &&
282             node.max === expectedMax &&
283             validate(node.left) &&
284             validate(node.right);
285    };
286
287    return validate(this.root);
288  }
289}
290
291// Kullanım örneği ve test
292const array = [1, 3, 5, 7, 9, 11];
293const segTree = new SegmentTree(array);
294
295// Aralık sorguları
296console.log('Sum [1,3]:', segTree.querySum(1, 3)); // 3 + 5 + 7 = 15
297console.log('Min [1,3]:', segTree.queryMin(1, 3)); // min(3, 5, 7) = 3
298console.log('Max [1,3]:', segTree.queryMax(1, 3)); // max(3, 5, 7) = 7
299
300// Nokta güncelleme
301segTree.updatePoint(2, 10); // index 2'deki değeri 10 yap
302console.log('Sum [1,3] after update:', segTree.querySum(1, 3)); // 3 + 10 + 7 = 20
303
304// Tree istatistikleri
305console.log('Tree statistics:', segTree.getStatistics());
306console.log('Tree is valid:', segTree.validateTree());

Zaman ve Alan Karmaşıklığı Analizi

Zaman Karmaşıklığı

Build Operation: O(n) - linear time
Range Query: O(log n) - logarithmic
Point Update: O(log n) - logarithmic
Range Update: O(log n) with lazy propagation
Space Usage: O(n) - linear space

Karşılaştırma

Naive Approach: O(n) query, O(1) update
Prefix Sum: O(1) query, O(n) update
Segment Tree: O(log n) query ve update
Square Root Decomposition: O(√n) both
Fenwick Tree: O(log n) - daha az memory

Lazy Propagation Optimizasyonu

Lazy propagation, aralık güncellemelerini etkili hale getiren bir tekniktir. Güncellemeyi hemen yapmak yerine, gerekli olana kadar erteler.

Normal Range Update

Zaman Karmaşıklığı: O(n log n)
Her güncelleme derhal yapılır
Çok sayıda gereksiz işlem
Basit implementasyon

Lazy Propagation

Zaman Karmaşıklığı: O(log n)
Güncelleme gerektiğinde yapılır
Minimum işlem sayısı
Karmaşık implementasyon

Segment Tree Variants ve Uzantılar

2D Segment Tree

İki boyutlu aralık sorguları için kullanılır. Matrix üzerinde rectangle sum, min veya max sorguları yapabilir.

Persistent Segment Tree

Historical queries destekler. Geçmiş versiyonlara erişim sağlar ve versiyonlanmış range queries yapar.

Dynamic Segment Tree

Koordinat compression ile çok büyük aralıkları handle eder. Sparse data için memory efficient.

Gerçek Dünya Uygulamaları

Software Development

Database Indexing: B+ tree range queries
Text Editors: Line-based operations
Graphics Programming: Spatial queries
Game Development: Collision detection

Data Analysis

Time Series: Moving window statistics
Financial Data: OHLC candlestick queries
Sensor Networks: Range monitoring
Log Analysis: Time range aggregations

Implementation ve Optimizasyon İpuçları

Memory Layout:Array-based implementation cache performance'ını artırabilir.
Build Optimization:Bottom-up build yaklaşımı recursive call overhead'ını azaltır.
Query Optimization:Tam kapsama durumunda erken return ile performance artırılır.
Lazy Propagation:Frequent range updates varsa mutlaka lazy propagation implementasyonu yapın.
Alternative:Sadece sum queries varsa Fenwick Tree daha memory efficient olabilir.

İleri Seviye Segment Tree Özellikleri

Lazy Propagation ile Range Update

// Lazy propagation örneği
class LazySegmentTree {
  updateRange(start, end, delta) {
    this.updateRangeLazy(this.root, start, end, delta);
  }
  
  updateRangeLazy(node, start, end, delta) {
    // Lazy value'yu push down et
    if (node.hasLazyValue) {
      node.sum += node.lazyValue * (node.end - node.start + 1);
      if (node.left) {
        node.left.lazyValue += node.lazyValue;
        node.left.hasLazyValue = true;
      }
      if (node.right) {
        node.right.lazyValue += node.lazyValue;
        node.right.hasLazyValue = true;
      }
      node.lazyValue = 0;
      node.hasLazyValue = false;
    }
    
    // Range update logic
    if (start <= node.start && end >= node.end) {
      node.lazyValue += delta;
      node.hasLazyValue = true;
      return;
    }
    
    // Partial overlap case
    const mid = Math.floor((node.start + node.end) / 2);
    if (start <= mid) {
      this.updateRangeLazy(node.left, start, end, delta);
    }
    if (end > mid) {
      this.updateRangeLazy(node.right, start, end, delta);
    }
  }
}

2D Segment Tree Örneği

// 2D Segment Tree temel yapısı
class SegmentTree2D {
  constructor(matrix) {
    this.rows = matrix.length;
    this.cols = matrix[0].length;
    this.tree = this.build2D(matrix);
  }
  
  // 2D aralık sorgusu
  queryRect(x1, y1, x2, y2) {
    return this.queryRows(0, 0, this.rows - 1, x1, x2, y1, y2);
  }
  
  queryRows(node, start, end, x1, x2, y1, y2) {
    if (x1 > end || x2 < start) return 0;
    
    if (x1 <= start && end <= x2) {
      return this.queryCols(this.tree[node], 0, this.cols - 1, y1, y2);
    }
    
    const mid = Math.floor((start + end) / 2);
    return this.queryRows(2*node+1, start, mid, x1, x2, y1, y2) +
           this.queryRows(2*node+2, mid+1, end, x1, x2, y1, y2);
  }
}

Competitive Programming İpuçları

Hızlı Template

• Array-based implementation kullanın (4*n boyut)
• 1-indexed arrays tercih edin (implementation kolaylığı)
• Recursive yerine iterative yaklaşım kullanın
• Macro'lar ile kod uzunluğunu azaltın

Debug Teknikleri

• Tree'yi print eden fonksiyon yazın
• Küçük test case'lerle doğrulayın
• Edge case'leri (tek eleman, boş dizi) test edin
• Lazy propagation'da push fonksiyonunu unutmayın

Performans Karşılaştırması ve Benchmarks

AlgoritmaBuildRange QueryPoint UpdateRange UpdateSpace
Naive ArrayO(1)O(n)O(1)O(n)O(n)
Prefix SumO(n)O(1)O(n)O(n)O(n)
Segment TreeO(n)O(log n)O(log n)O(log n)O(4n)
Fenwick TreeO(n)O(log n)O(log n)O(n log n)O(n)
√n DecompositionO(n)O(√n)O(√n)O(√n)O(n)

Yaygın Hatalar ve Çözümleri

❌ Yanlış Array Boyutu

Segment tree için 4*n boyutunda array kullanmamak overflow'a neden olur.

// Yanlış: tree = new Array(2*n)
// Doğru: tree = new Array(4*n)

❌ Lazy Propagation Unutmak

Range update sonrası query yapmadan önce push fonksiyonunu çağırmamak.

// Her query/update başında push() çağırmalı

❌ Edge Case Kontrolsüzlüğü

Boş aralık sorguları ve geçersiz indeksler için kontrol yapmamak.

if (queryStart > queryEnd || queryEnd < nodeStart) return neutral;