Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### maxorand's blog

By maxorand, 5 years ago,

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 × 2k (or maybe something like this 2 × 2k + 5) where k = ⌈ log2N, won't that be enough? If not, then why?

• 0

 » 5 years ago, # |   0 2*N is enough.
•  » » 5 years ago, # ^ |   0 No, 2 * N will not hold for any N that is not a power of 2. For example if N = 105 then you will need roughly 262143 sized segment tree, which is greater than 2 * N. Actually 4 * N is the safest way.
•  » » » 5 years ago, # ^ |   +5 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
 » 5 years ago, # | ← Rev. 2 →   -8 Actually if you can write N as 2x where x is an integer then you can see that you need 2x + 1 - 1 nodes in your segment tree. So what can you do for other N's? Well, you can find the next power of 2 after N, let's say it is 2x and then you can declare 2x + 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 * N with your eyes closed!
 » 5 years ago, # |   -7 Here is a nice Quora answer which proves that 4 is in fact the smallest k such that kN is enough space for a segment tree on an array of size N.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 But iterative segment tree takes only 2N space. const int N = 100005; int n, a[N], t[N + N]; void init() { for (int i = 0; i < n; ++i) { t[n + i] = a[i]; } for (int i = n - 1; i; --i) { t[i] = t[i << 1] + t[i << 1 | 1]; } } See more here.
•  » » » 5 years ago, # ^ |   0 Sure, the page I linked to assumes the recursive implementation, so the result it proves is not valid for the iterative implementation you suggest.
•  » » » » 3 years ago, # ^ |   0 https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/#c191521in here segment tree has 2*n-1 size even in recursive implementation
 » 5 years ago, # |   0 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 N elements, then I will find the minimum M = 2m that is no less than N. Then, the total number of nodes in the segment tree should be 2 * M.
 » 3 years ago, # |   +1 You should change a little bit k=(int)log2(N)+1; Rest of them are ok .
 » 3 years ago, # | ← Rev. 2 →   0 Your solution fail for N=7 . According to you Size=2* (2^2) = 8 . But this is wrong because in tree , the leftmost node of lower level is 8 and the rightmost node of lower level is 13 . That's why it fails . Your fault is that your logarithm just chopped some fractional number . FIrst you have to calculate the leftmost node of the lower level , which is 2^k , where k=log2(N)+1 ; . We have to multiply 2^k by 2 . Because we know that in each level there has 2^i nodes . So in the lowest level there has 2^k nodes . So the rightmost node is 2^k + 2^k = 2* 2^k . That's why it works for 2 times 2^k
•  » » 3 years ago, # ^ |   0 maxorand watch my answer .