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: &
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 ▸