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 :)
Auto comment: topic has been updated by Aslan_Aslanli (previous revision, new revision, compare).
Setting dfs order fills the gap and reduces the memory to 2n-1.
iterativeSegTree.cpp
A simpler proof: First consider the base case n = 1. The segment tree has exactly one node, so the formula holds. Whenever n increases by 1, one leaf node in the segment tree gains two children, increasing the total number of nodes by 2.
Damn :x
Where did the 4*MAXN thing even come from? I'm guessing people extending the array to next power of 2 because "easier implementation"?
Nah 4*n is necessary for recursive approach since we are moving top to bottom, since blocks can be on different level if it is not a perfect power of 2, u end up doing 2*index,2*index+1 for indexes that didnt need it(we already got to leaf on that side) but since other side was pending it went deeper, this gives segmentation fault since those indexes dont exist on one side, so we have to create dummy nodes aka 4*n to ensure it is a perfect binary tree and we dont go out of bound.
Iteration works bottom up, so we guarentee to start from the leaves and end at the top hence assigning 2*n doesnt make it out of bound since we are never accessing out of bound index at any level.
or you could do 2*n and have an if statement in your recursion function to terminate if the node index is higher than that.
(or just use iterative, less code and better constant factor)
Ya ik its possible that way as well but writing conditional is kinda going off better to declare 4*n instead, as for the iterative, yes Iterative is much better though the only issue is it can be hard to understand for someone who hasnt practiced much of seg tree.
Still, 4 * n is safe, and there are VERY few cases where your code fails because you didn't optimize it from 4 * n to 2 * n
We can use recursive seg tree with just $$$2*n-1$$$ nodes allocated! This is possible because we know the size of lower levels, so if we are now in a level covering range $$$[l,r]$$$ in index $$$i$$$, the interval in the node vector $$$[i,i+2*(r-l+1)-1]$$$ represents this subtree. To do that, if the middle point is $$$mid$$$, then the left subtree would be in the range $$$[i+1,i+2*(mid-l+1)-1]$$$ and the right subtree would be in the range $$$[i+2*(mid-l+1),i+2*(r-l+1)-1]$$$. The way of accssing is something like:
You can also see this in cp-algorithms: https://cp-algorithms.com/data_structures/segment_tree.html#memory-efficient-implementation
Set node index to (l+r) | (l!=r), then only 2*n length of array is enough. This is kinda weird but somehow correct. Also this way only leaves will have even indexes.
correctness:
edit: I wanted to point out you can do 3n lazy seg with the following mapping:
f(l,r) -> l==r ? n-1+l : (l+r)/2