Segment tree space requirement

Question

I have found as explained in this article on HackerEarth that segment trees can be implemented by using arrays where child elements of a node positioned at array-index n are at indexes 2n and 2n+1.

Also it states that for storing n elements in my segment tree, I need 2n+1 nodes.

Yet recently when I solved few problems related to segment trees, sometimes my code gave runtime error which got resolved when I changed the array size for storing the segment tree to 4 x (size of array to be stored in segment tree). How can I be sure that a segment tree actually requires 4n-sized array for n elements.

Answer 1

If you are good at Russian, read this article: http://e-maxx.ru/algo/segment_tree

If you are not, I'll describe, what it is saying about: We need to notice, that the size of the array you contain the segment tree in, using such enumeration (where left child of i is 2i and right child is 2i+1), will be not 2n, but 4n. The thing is: this enumeration doesn't work completely fine when n is not a power of 2 - in this case we get "skipped" numbers, that are not assigned to any tree vertices (they mean "nodes"). Actually, it works as if we rounded n up to the closest power of 2. It doesn't make the implementation more complicated, but compels us to increase the size of the array to 4n.

Edit: Here is the English-version of the above-referenced article: https://cp-algorithms.com/data_structures/segment_tree.html

Answer 2

The 2N+1 nodes works with the given way to locate the children if N is one less than a power of 2 (or if the tree is balanced and the missing leaf nodes are all at the right of the bottom row, similar to the first tree diagram in the article). Otherwise doubling the index of a node to get its children will go past the bounds of the array. Look at the middle diagram from the article (the tree with "36" in the top node). The "16" node would have index 6, so its children would be at nodes 12 and 13. Node "5" does not have any children (which should be in nodes 10 and 11). These missing nodes will still need to have slots in the array for them.