#6620. 更新路径模拟(4)
更新路径模拟(4)
题目 4:更新路径模拟
题目描述
树状数组单点修改 add(x, v) 时,路径变化规则为:
x = x + lowbit(x)
给定数组长度 n 和起点 x,请输出执行 add(x, v) 时会更新的所有树状数组下标。
输入格式
输入两个整数:
n x
输出格式
按顺序输出会被更新的下标。
数据范围
1 ≤ x ≤ n ≤ 10^9
样例输入
16 5
样例输出
5 6 8 16
样例解释
x = 5,lowbit(5) = 1,下一个位置是 6
x = 6,lowbit(6) = 2,下一个位置是 8
x = 8,lowbit(8) = 8,下一个位置是 16
x = 16,lowbit(16) = 16,下一个位置是 32
32 > 16,停止
所以更新:
bit[5], bit[6], bit[8], bit[16]