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
+1-1Lines changed: 1 addition & 1 deletion
Original file line number
Diff line number
Diff line change
@@ -44,7 +44,7 @@ Here is a visual representation of such a Segment Tree over the array $a = [1, 3
44
44
45
45
From this short description of the data structure, we can already conclude that a Segment Tree only requires a linear number of vertices.
46
46
The first level of the tree contains a single node (the root), the second level will contain two vertices, in the third it will contain four vertices, until the number of vertices reaches $n$.
47
-
Thus the number of vertices in the worst case can be estimated by the sum $1 + 2 + 4 + \dots + 2^{\lceil\log_2 n\rceil}= 2^{\lceil\log_2 n\rceil + 1} \lt 4n$.
47
+
Thus the number of vertices in the worst case can be estimated by the sum $1 + 2 + 4 + \dots + 2^{\lceil\log_2 n\rceil}\lt 2^{\lceil\log_2 n\rceil + 1} \lt 4n$.
48
48
49
49
It is worth noting that whenever $n$ is not a power of two, not all levels of the Segment Tree will be completely filled.