AQZZ's blog

Segment Tree Question
By AQZZ, history, 4 years ago, In English

Recently I've been learning about segment tree from here: https://cp-algorithms.com/data_structures/segment_tree.html and I am wondering why they allocate an array of size 4 * N when the tree uses indices up to at most 2 * 2^(ceil(log2(N)). In the worst case, when N = 1 + 2^k for some integer k > 0, say N = 65, then they allocate 260 when only 256 is needed, but in my submissions, using the optimized memory amount cut the memory usage by 13% or more. My guess would be that the memory optimization usually isn't necessary for C++ (being one of the most efficient languages) and its more convenient to type 4 * N than 2 * (1 << int(ceil(log2l(N)))). P.S. if anyone knows a better way to get the smallest power of 2 greater than or equal to x I would like to know.

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Amount of memory to allocate for internal data depends on the set of operations you want to perform with segment trees. Sometimes it is enough to have 2n-1 (actually 2n with one more item as a sentinel), but there are cases when you need 4n. I guess you have just seen some general implementation.

Update

uint32_t next_power_of_2(uint32_t x)   
{ 
    --x; 
    x |= x >> 1; 
    x |= x >> 2; 
    x |= x >> 4; 
    x |= x >> 8; 
    x |= x >> 16; 
    return ++x; 
}
→ Reply