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

Commitee256b1

Browse files
jxuadamant-pwn
authored andcommitted
Add implicit tree indexing details
1 parent3691375 commitee256b1

File tree

1 file changed

+1
-0
lines changed

1 file changed

+1
-0
lines changed

‎src/data_structures/segment_tree.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -163,6 +163,7 @@ We will use a simple trick to make this a lot more efficient of using an _implic
163163
(A similar method is used for binary heaps).
164164
The sum of the root vertex at index 1, the sums of its two child vertices at indices 2 and 3, the sums of the children of those two vertices at indices 4 to 7, and so on.
165165
With 1-indexing, conveniently the left child of a vertex at index $i$ is stored at index $2i$, and the right one at index $2i + 1$.
166+
Equivalently, the parent of a vertex at index $i$ is stored at $i/2$ (integer division).
166167

167168
This simplifies the implementation a lot.
168169
We don't need to store the structure of the tree in memory.

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp