Function to find prefix sum upto idx
def queryBIT ( idx ) : NEW_LINE INDENT 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