Query function in bit
def pref ( idx ) : NEW_LINE INDENT global bit NEW_LINE ans = 0 NEW_LINE while idx > 0 : NEW_LINE INDENT ans += bit [ idx ] NEW_LINE idx -= ( idx & - idx ) NEW_LINE DEDENT return ans NEW_LINE DEDENT