You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/data_structures/segment_tree.md
+2-2Lines changed: 2 additions & 2 deletions
Original file line number
Diff line number
Diff line change
@@ -602,7 +602,7 @@ This leads to a construction time of $O(n \log^2 n)$ (in general merging two red
602
602
The $\text{query}$ function is also almost equivalent, only now the $\text{lower_bound}$ function of the $\text{multiset}$ function should be called instead ($\text{std::lower_bound}$ only works in $O(\log n)$ time if used with random-access iterators).
603
603
604
604
Finally the modification request.
605
-
To process it, we must go down the tree, and modify all $\text{multiset}$ from the corresponding segments that contain theeffected element.
605
+
To process it, we must go down the tree, and modify all $\text{multiset}$ from the corresponding segments that contain theaffected element.
606
606
We simply delete the old value of this element (but only one occurrence), and insert the new value.
607
607
608
608
```cpp
@@ -682,7 +682,7 @@ other Segment Trees (somewhat discussed in [Generalization to higher dimensions]
682
682
683
683
###Range updates (Lazy Propagation)
684
684
685
-
All problems in the above sections discussed modification queries that onlyeffected a single element of the array each.
685
+
All problems in the above sections discussed modification queries that onlyaffected a single element of the array each.
686
686
However the Segment Tree allows applying modification queries to an entire segment of contiguous elements, and perform the query in the same time $O(\log n)$.