#6619. 查询路径模拟(3)

查询路径模拟(3)

题目 3:查询路径模拟

题目描述

树状数组查询前缀和 sum(x) 时,路径变化规则为:

x = x - lowbit(x)

给定一个整数 x,请输出查询 sum(x) 时访问的所有下标,直到 x = 0 为止。


输入格式

输入一个整数 x

输出格式

按顺序输出查询路径中的所有下标,最后输出 0


数据范围

1 ≤ x ≤ 10^9

样例输入

13

样例输出

13 12 8 0

样例解释

13 = 1101₂,lowbit(13) = 1,13 - 1 = 12
12 = 1100₂,lowbit(12) = 4,12 - 4 = 8
8 = 1000₂,lowbit(8) = 8,8 - 8 = 0

所以路径是:

13 → 12 → 8 → 0