segment tree for adding a array with single index updates
I'd implement next_power_2 like this, using int.bit_length:

def next_power_2(n):
    "If n &gt; 0, return smallest power of 2 greater than or equal to n."
    return 1 &lt;&lt; (n - 1).bit_length()


This is more than twice as fast as than the version in the post, and it works for arbitrarily large integers.