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.

Note that the `left child(N) = 2N; right child(N) = 2N+1` system works for a simple binary tree but only when starting from N=1, not when starting with N=0. You can fix it up so it does work from N=0, but it is slightly different formulae (LC(N) = 2N+1; RC(N)=2N+2). I'm not clear why you'd need 2N+1 nodes to store a tree with N entries; N is enough if you can allocate so that the first element is indexed at 1, and N+1 is sufficient if you allocate from 0 but only use from 1. Neither is inflated by a factor of 2. _[…continued…]_ — Jonathan Leffler, Sep 17 '16 at 01:55
_[…continuation…]_ There might be reasons in the article — it is storing ranges and if each range occupies two cells, then you need to double up; but the article is long and your question is not really well suited to SO. You should demonstrate why you find yourself needing to use 4N with some code, and we can validate it. Or something. — Jonathan Leffler, Sep 17 '16 at 01:59
Not sure; I don't frequent many other Stack Exchange sites. You could look at Programmers, but I'm not at all sure they'd be OK with it. I thought there's a computer science site too; ditto — but I can't find it on the list of all sites. You can rescue the question for SO by showing code implementing the 4N stuff and checking whether that's necessary. I looked at the article a bit harder and it seems to have an extra layer of nodes over and above what I'd expect (for N=7, it has a whole bunch of nodes requiring something like 13 nodes in total; I've not worked out why yet). — Jonathan Leffler, Sep 17 '16 at 02:16
On further search I found this link, but can't understand it, is there some simpler explanation: https://www.quora.com/Why-does-4-%2A-N-space-have-to-be-allocated-for-a-segment-tree-where-N-is-the-size-of-the-original-array/answer/Brian-Bi?srid=iHMe — brijs, Sep 17 '16 at 02:24
https://discuss.codechef.com/questions/85040/size-of-segment-tree — Rohith R, Sep 17 '16 at 03:07

score 10 · Accepted Answer · edited Jan 18 '20 at 20:22

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

score 2 · Answer 2 · answered Sep 17 '16 at 03:30

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.

Segment tree space requirement

2 Answers2