Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit14552cf

Browse files
authored
Fix typo with size estimation for segment tree (#1)
* Fix typo with size estimation for segment tree
1 parent4645c92 commit14552cf

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

‎src/data_structures/segment_tree.md

Lines changed: 1 addition & 1 deletion
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.

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp