If the given array's size is *N* then what should I declare the size of the array for Segment Tree?

If I set the Segment Tree's array size to 2 × 2^{k} (or maybe something like this 2 × 2^{k} + 5) where *k* = ⌈ *log*_{2}*N*⌉, won't that be enough? If not, then why?

2*N is enough.

No, 2 *

Nwill not hold for anyNthat is not a power of 2.For example if

N= 10^{5}then you will need roughly 262143 sized segment tree, which is greater than 2 *N. Actually 4 *Nis the safest way.2*N is sufficient size for a segment array(irrespective of whether N is a power of 2 or not).Here's an article about the approach to do it: http://codeforces.com/blog/entry/18051

Actually if you can write

Nas 2^{x}wherexis an integer then you can see that you need 2^{x + 1}- 1 nodes in your segment tree. So what can you do for otherN's? Well, you can find the next power of 2 afterN, let's say it is 2^{x}and then you can declare 2^{x + 1}- 1 sized segment tree. So yes it will work as you said.But if you don't want to do that much calculation, you can always declare 4 *

Nwith your eyes closed!Here is a nice Quora answer which proves that 4 is in fact the smallest

ksuch thatkNis enough space for a segment tree on an array of sizeN.But iterative segment tree takes only 2

Nspace.See more here.

Sure, the page I linked to assumes the recursive implementation, so the result it proves is not valid for the iterative implementation you suggest.

I usually adopt the implementation of segment tree mentioned in this book Competitive Programmer's Handbook — a new book on competitive programming.

According to my own understanding, if there are

Nelements, then I will find the minimumM= 2^{m}that is no less than N. Then, the total number of nodes in the segment tree should be 2 *M.You should change a little bit k=(int)log2(N)+1; Rest of them are ok .