Repository navigation
segment tree translated, lazy and binary search added - #87
Conversation
muratbiberoglu
left a comment
muratbiberoglu
left a comment
There was a problem hiding this comment.
I entered some suggestions about translation and formatting. Thank you for your effort and contribution 🙌
| --- | ||
|
|
||
| Segment Tree bir dizide $\mathcal{O}(\log N)$ zaman karmaşıklığında herhangi bir $[l,r]$ aralığı icin minimum, maksimum, toplam gibi sorgulara cevap verebilmemize ve bu aralıklar üzerinde güncelleme yapabilmemize olanak sağlayan bir veri yapısıdır. | ||
| # Segment Tree |
There was a problem hiding this comment.
We can remove this. title property in the meta part of this file is automatically added as h1 tag.
| ## Yapısı ve Kuruluşu | ||
| Segment Tree, "Complete Binary Tree" yapısına sahiptir. Segment Tree'nin yaprak düğümlerinde dizinin elemanları saklıdır ve bu düğümlerin atası olan her düğüm kendi çocuğu olan düğümlerinin cevaplarının birleşmesiyle oluşur. Bu sayede her düğümde belirli aralıkların cevapları ve root düğümünde tüm dizinin cevabı saklanır. Örneğin toplam sorgusu için kurulmuş bir Segment Tree yapısı için her düğümün değeri çocuklarının değerleri toplamına eşittir. | ||
| ## Structure and Construction | ||
| Segment Tree has a "Complete Binary Tree" structure. The leaf nodes of the Segment Tree store the elements of the array, and each node's value is the sum of its children's values. Thus, the answers of certain intervals are stored in each node, and the answer of the whole array is stored in the root node. For example, for a Segment Tree structure built for the sum query, the value of each node is equal to the sum of its children's values. |
There was a problem hiding this comment.
Instead of below part:
The leaf nodes of the Segment Tree store the elements of the array, and each node's value is the sum of its children's values.
We can use this:
The leaf nodes of the Segment Tree store the elements of the array, and each internal node's value is calculated with a function that takes its children's values as inputs.
| @@ -37,65 +37,307 @@ void build(int ind, int l, int r) { | |||
|
|
|||
| ### Sorgu Algoritması | |||
There was a problem hiding this comment.
We can change it as Query Algorithm
| } | ||
| ``` | ||
|
|
||
| ### Eleman Güncelleme Algoritması |
There was a problem hiding this comment.
We can change it as Update Algorithm
|
|
||
| Dizideki $x$ indeksli elemanının değerini güncellemek için kullanılan algoritma şu şeklide çalışır: | ||
| The algorithm used to update the value of the $x$ indexed element in the array works as follows: | ||
| - The value of the leaf node containing the $x$ indexed element is updated. |
There was a problem hiding this comment.
We can use this: Update the value of every node that contains
| A sample problem related to the Segment Tree data structure can be found [here](https://codeforces.com/gym/100739/problem/A){target="_blank"}. | ||
|
|
||
| ## Segment Tree with Lazy Propagation | ||
| Previously, update function was called to update only a single value in array. Please |
There was a problem hiding this comment.
We can remove new line characters in this paragraph.
| - Return the sum of all elements in the given range $[l, r]$. | ||
|
|
||
| Notice that if update was for single element, we could use the segment tree we have learned before. | ||
| Trivial structure comes to mind is to use an array and do the operations by traversing and increasing |
There was a problem hiding this comment.
Also here we can remove new line characters in this paragraph.
| takes $\mathcal{O}(\log^{2} M)$ time, but we can do better. | ||
|
|
||
| ### How To Speed Up? | ||
| If you look at the segment tree solution on preceding subsection you can see that queries are performed |
There was a problem hiding this comment.
Until here we can remove new line characters in this paragraph 😂
2 participants
No description provided.