Hello. I was wondering why we always make a segment tree's length 4*n. So, I went ahead and tried to prove it, and in the end, I was able to prove that the number of nodes is exactly 2*n-1. So, I want to share it.

Now, first of all, let's initially prove why it works when n is a power of 2, so let's say that n=2^k. We construct the tree (I am gonna put it's picture too), and we can see that there are n leaves.

Because each two leaves combine to make another parent (node), we can say that those leaves have n/2 parents, those parents have n/4 parents, n/8, n/16, and at the end, there is only a single node left, which is our initial segment (1->n). Now, we can use simple math in order to calculate the number of nodes. Let's say that the number of nodes is S. We can see that S=n + n/2 + n/4 + n/8 + ...... + 1, which is a geometric progression where the a=n, the number of element which we sum up is k+1 (because n is 2^k), and the r=1/2. Using the geometric progression sum formula, we get S=(n*(1-((1/2)^(k+1))))/(1-1/2), and because n=2^k, S=(2^k-(1/2))/(1/2), and finally S=2^(k+1)-1. Once again, because n=2^k, S=2*n-1.

Okay, now that we got that out of the way, why is that formula correct for any given number n? Let's say n=2^k + h where k=log2(n). That means that h<2^k. Now, when we construct the array this way, we can see one very important thing. I am going to explain it with an example, and I am going to put a picture about it (please note that in the picture, instead of using a segment for each node, I am gonna use the length of that segment).

So let's look at the examples 8 and 9. Notice how when we increase 8 by one, up until the last leave, the overall number of nodes do not change. It becomes even more clear when we look at the example with 8 and 10, in which the overall number of nodes do not change until the last moment, even though the length of the segment covered by that node do change.

And finally, we can see that each added number adds two additional nodes to the overall tree, which means that S = 2^(k+1) — 1 + 2*h, S = 2^(k+1) + 2*h — 1, S = 2 * (2^k + h) — 1. And because n=2^k+h, S = 2*n-1.

Now, the problem is that when you do make the seg tree recursively, you kinda look at "Ghost nodes", so in recursive implementation, you cannot set the length of the segment tree anything lower than 4*n. BUUUUUTTTT, if you were to implement it iteratively, you would be able to set the length 2*n, which would save you some memory. This is mainly used in international olimpiads where the memory limit is too tight to set it 4*n.

I hope that this was useful, and although it is not a rare find (A lot of people are aware of this), I just wanted to show the proof I did and maybe some people can benefit from this blog too. Cya :)