Блог пользователя AQZZ

Segment Tree Question
Автор AQZZ, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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; 
}
→ Ответить