$ ./guess_the_languageProblem Solving — fill the blank
Problem Solving — fill the blank · hard · #330

What goes in the blank?

# Fenwick tree prefix sum of [1..i]
s = 0
while i > 0:
    s += tree[i]
    i -= i ____ -i
return s

Answer: & (also accepted: &)

i & -i is the lowest set bit of i, the size of the range tree[i] covers. Removing it jumps to the previous disjoint range.
Play Problem Solving ▸