Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
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.
Segment Tree (Aralık Ağacı) Veri Yapısı algoritmasının farklı programlama dillerindeki uygulamaları aşağıda verilmiştir. Her örnek, algoritmanın temel akışını açık şekilde gösterecek biçimde sunulmuştur.
1function segmentTreeAralKAAcVeriYapS(input) {2 // Pseudocode logic applied to JavaScript runtime3 return {4 input,5 algorithm: 'Segment Tree (Aralık Ağacı) Veri Yapısı',6 complexity: 'O(log n)',7 };8}Aşağıya kendi verilerinizi girerek algoritmanın örnek çalışma akışını görebilirsiniz. Virgülle ayrılmış sayılar veya metin değerleri kullanabilirsiniz.
Girilen veri, algoritmanın pseudo kodundaki genel akışa göre örnek bir sonuca dönüştürülür.
En İyi Durum: O(log n)
Ortalama Durum: O(log n)
En Kötü Durum: O(log n)
O(n) - Çalışma süresi, giriş boyutu ile doğrusal olarak artar.
Segment Tree (Aralık Ağacı) Veri Yapısı ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:
Bu kullanım alanı, algoritmanın benzer problem aileleriyle birlikte incelenmesi için iyi bir başlangıç noktasıdır.
Bu kullanım alanı, algoritmanın benzer problem aileleriyle birlikte incelenmesi için iyi bir başlangıç noktasıdır.
Bu kullanım alanı, algoritmanın benzer problem aileleriyle birlikte incelenmesi için iyi bir başlangıç noktasıdır.
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.
• 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
Zaman Karmaşıklığı:
Alan Karmaşıklığı: O(ALPHABET_SIZE * N * M)
Kullanım Alanları: Otomatik tamamlama, yazım kontrolü, IP routing
Zaman Karmaşıklığı:
Alan Karmaşıklığı: O(n)
Kullanım Alanları: Aralık toplamı, min/max sorguları, lazy propagation
Dizi, başlangıç indeks ve bitiş indeks girerek aralık sorgusu yapın
Belirli bir indeksteki değeri güncelleyin
Segment Tree veri yapısının tam JavaScript implementasyonu. Aralık sorguları, nokta güncellemeleri ve tree validasyonu özellikleri içerir.
1// Segment Tree JavaScript implementasyonu2class SegmentTreeNode {3 constructor(start, end, sum = 0, min = Infinity, max = -Infinity) {4 this.start = start;5 this.end = end;6 this.sum = sum;7 this.min = min;8 this.max = max;9 this.left = null;10 this.right = null;11 this.lazyValue = 0;12 this.hasLazyValue = false;13 }14}1516class SegmentTree {17 constructor(array) {18 this.originalArray = [...array];19 this.root = array.length > 0 ? this.buildTree(array, 0, array.length - 1) : null;20 }2122 buildTree(array, start, end) {23 if (start === end) {24 return new SegmentTreeNode(25 start, 26 end, 27 array[start], 28 array[start], 29 array[start]30 );31 }3233 const mid = Math.floor((start + end) / 2);34 const leftChild = this.buildTree(array, start, mid);35 const rightChild = this.buildTree(array, mid + 1, end);3637 const node = new SegmentTreeNode(start, end);38 node.left = leftChild;39 node.right = rightChild;40 41 node.sum = leftChild.sum + rightChild.sum;42 node.min = Math.min(leftChild.min, rightChild.min);43 node.max = Math.max(leftChild.max, rightChild.max);4445 return node;46 }4748 querySum(queryStart, queryEnd) {49 if (!this.root || queryStart > queryEnd) return 0;50 return this.querySumHelper(this.root, queryStart, queryEnd);51 }5253 queryMin(queryStart, queryEnd) {54 if (!this.root || queryStart > queryEnd) return Infinity;55 return this.queryMinHelper(this.root, queryStart, queryEnd);56 }5758 queryMax(queryStart, queryEnd) {59 if (!this.root || queryStart > queryEnd) return -Infinity;60 return this.queryMaxHelper(this.root, queryStart, queryEnd);61 }6263 updatePoint(index, newValue) {64 if (!this.root || index < 0 || index >= this.originalArray.length) return;65 this.originalArray[index] = newValue;66 this.updatePointHelper(this.root, index, newValue);67 }6869 updateRange(updateStart, updateEnd, delta) {70 if (!this.root || updateStart > updateEnd) return;71 for (let i = updateStart; i <= updateEnd; i++) {72 if (i >= 0 && i < this.originalArray.length) {73 this.originalArray[i] += delta;74 }75 }76 this.root = this.buildTree(this.originalArray, 0, this.originalArray.length - 1);77 }7879 querySumHelper(node, queryStart, queryEnd) {80 if (queryStart <= node.start && queryEnd >= node.end) return node.sum;81 if (queryEnd < node.start || queryStart > node.end) return 0;8283 let result = 0;84 if (node.left) result += this.querySumHelper(node.left, queryStart, queryEnd);85 if (node.right) result += this.querySumHelper(node.right, queryStart, queryEnd);86 return result;87 }8889 queryMinHelper(node, queryStart, queryEnd) {90 if (queryStart <= node.start && queryEnd >= node.end) return node.min;91 if (queryEnd < node.start || queryStart > node.end) return Infinity;9293 let leftMin = Infinity;94 let rightMin = Infinity;95 if (node.left) leftMin = this.queryMinHelper(node.left, queryStart, queryEnd);96 if (node.right) rightMin = this.queryMinHelper(node.right, queryStart, queryEnd);97 return Math.min(leftMin, rightMin);98 }99100 queryMaxHelper(node, queryStart, queryEnd) {101 if (queryStart <= node.start && queryEnd >= node.end) return node.max;102 if (queryEnd < node.start || queryStart > node.end) return -Infinity;103104 let leftMax = -Infinity;105 let rightMax = -Infinity;106 if (node.left) leftMax = this.queryMaxHelper(node.left, queryStart, queryEnd);107 if (node.right) rightMax = this.queryMaxHelper(node.right, queryStart, queryEnd);108 return Math.max(leftMax, rightMax);109 }110111 updatePointHelper(node, index, newValue) {112 if (node.start === node.end) {113 node.sum = newValue;114 node.min = newValue;115 node.max = newValue;116 return;117 }118119 const mid = Math.floor((node.start + node.end) / 2);120 if (index <= mid && node.left) {121 this.updatePointHelper(node.left, index, newValue);122 } else if (node.right) {123 this.updatePointHelper(node.right, index, newValue);124 }125126 if (node.left && node.right) {127 node.sum = node.left.sum + node.right.sum;128 node.min = Math.min(node.left.min, node.right.min);129 node.max = Math.max(node.left.max, node.right.max);130 }131 }132133 getTreeStructure() {134 return this.root;135 }136137 getHeight() {138 return this.getHeightHelper(this.root);139 }140141 getHeightHelper(node) {142 if (!node) return 0;143 const leftHeight = this.getHeightHelper(node.left);144 const rightHeight = this.getHeightHelper(node.right);145 return 1 + Math.max(leftHeight, rightHeight);146 }147148 getArray() {149 return [...this.originalArray];150 }151152 getStatistics() {153 let nodeCount = 0;154 let leafCount = 0;155156 const traverse = (node) => {157 if (!node) return;158 nodeCount++;159 if (node.start === node.end) leafCount++;160 traverse(node.left);161 traverse(node.right);162 };163164 traverse(this.root);165166 return {167 nodeCount,168 leafCount,169 height: this.getHeight(),170 arraySize: this.originalArray.length171 };172 }173174 validateTree() {175 if (!this.root) return true;176177 const validate = (node) => {178 if (!node) return true;179 if (node.start === node.end) {180 const expectedValue = this.originalArray[node.start];181 return node.sum === expectedValue && 182 node.min === expectedValue && 183 node.max === expectedValue;184 }185 if (!node.left || !node.right) return false;186187 const expectedSum = node.left.sum + node.right.sum;188 const expectedMin = Math.min(node.left.min, node.right.min);189 const expectedMax = Math.max(node.left.max, node.right.max);190191 return node.sum === expectedSum &&192 node.min === expectedMin &&193 node.max === expectedMax &&194 validate(node.left) &&195 validate(node.right);196 };197198 return validate(this.root);199 }200}// Lazy propagation örneği
class LazySegmentTree {
updateRange(start, end, delta) {
this.updateRangeLazy(this.root, start, end, delta);
}
updateRangeLazy(node, start, end, delta) {
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;
}
if (start <= node.start && end >= node.end) {
node.lazyValue += delta;
node.hasLazyValue = true;
return;
}
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 temel yapısı
class SegmentTree2D {
constructor(matrix) {
this.rows = matrix.length;
this.cols = matrix[0].length;
this.tree = this.build2D(matrix);
}
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);
}
}| Algoritma | Build | Range Query | Point Update | Range Update | Space |
|---|---|---|---|---|---|
| Naive Array | O(1) | O(n) | O(1) | O(n) | O(n) |
| Prefix Sum | O(n) | O(1) | O(n) | O(n) | O(n) |
| Segment Tree | O(n) | O(log n) | O(log n) | O(log n) | O(4n) |
| Fenwick Tree | O(n) | O(log n) | O(log n) | O(n log n) | O(n) |
| √n Decomposition | O(n) | O(√n) | O(√n) | O(√n) | O(n) |
Segment tree için 4*n boyutunda array kullanmamak overflow'a neden olur.
Range update sonrası query yapmadan önce push fonksiyonunu çağırmamak.
Boş aralık sorguları ve geçersiz indeksler için kontrol yapmamak.