8000 Fix typo with size estimation for segment tree (#1) · cp-algorithms/cp-algorithms@14552cf · GitHub
[go: up one dir, main page]

Skip to content

Commit 14552cf

Browse files
authored
Fix typo with size estimation for segment tree (#1)
* Fix typo with size estimation for segment tree
1 parent 4645c92 commit 14552cf

File tree

Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ Here is a visual representation of such a Segment Tree over the array $a = [1, 3
4444

4545
From this short description of the data structure, we can already conclude that a Segment Tree only requires a linear number of vertices.
4646
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$.
4848

4949
It is worth noting that whenever $n$ is not a power of two, not all levels of the Segment Tree will be completely filled.
5050
We can see that behavior in the image.