Array size in segment tree Data structure

Question

In segment tree, we build segment tree above an array.
For Example, If array size is 8 [0-7] indexing.
Number of nodes in segment tree is 15 i.e., 1,2,4,8 in 1st,2nd,3rd,4th levls

But in a problem, if I declare structure array size as seg tree[2*N + 1] its giving wrong answer whereas if I declare it as below

struct seg{ 
 int sum;
};
seg tree[4*N + 1];

Its giving wrong answer. My doubt is that [2*N] is sufficient, Then why is it giving wrong answer.
Node segment(1-1) having number 9 its parent have number 4. So left child is 2*N right child is 2*N+1

@ShubhamBhattar Its fixed. It might have given Compile Error? But Its giving WA if i change it to 2*N — Sparrow, Jul 20 '16 at 15:19

score 0 · Answer 1 · edited May 23 '17 at 12:22

0

Let n be the size of the initial array. The size of the segment tree will be:

2*n-1 if n is a power of 2.
2*2^(log_2(n)+1)-1 if n is not a power of 2.

Edit: It's true that we can create just an array of size 2*n-1 to make a tree theoretically, but think about the how we can go from parent to children in the array representation of segment tree? The left child will be at index 2*i+1 (0-based indexing) and the right child will be at index 2*i+2. To maintain this invariant, we have to construct the complete binary tree and for that the formula is mentioned above.

You can also refer this.

edited May 23 '17 at 12:22

Community

1
1

answered Jul 20 '16 at 15:36

Shubham

2,847
4
24
37

In either ways the size should be less than __2*N__. For any given **n** the maximum value node number is **2*N-1**. – Sparrow Jul 23 '16 at 11:28
_Induction_ : 1-1, 2-3, 3-5, 4-9, 5-9, 6-11, 7-13,...,N - 2N-1 – Sparrow Jul 23 '16 at 11:32
For `n=5`, the size of the segment tree will be 15 not 10. – Shubham Jul 23 '16 at 11:38
How come 15. For n = 5, if the number of the segment [0-4] is 1, then max node value occurs at [1-1] (number 9, i.e., 2*N - 1) – Sparrow Jul 23 '16 at 12:03
Did you look at the formula above? If `n=5`, `log_2(5) = 2`, `2*(2^(2+1))-1 = 15`. – Shubham Jul 23 '16 at 12:06
It might be wrong. As you can see its 9 which is the max node value; I have updated the **figure**. See it – Sparrow Jul 23 '16 at 12:17
Try to draw a segment tree for range 1 to 10, and you will see that an array of size 19 is not sufficient to hold all the nodes. – Fanchen Bao Jun 26 '21 at 21:08

Array size in segment tree Data structure

1 Answers1