Segment Tree Question

Правка en1, от AQZZ, 2020-06-30 07:55:59

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.

Теги #segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AQZZ 2020-06-30 07:55:59 788 Initial revision (published)