#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