5975专题

hdu 5975 树状数组原理题(16亚洲区域赛大连站)

lowbit[i]表示的其实就是i的二进制表示中,不为0的最低位;对于询问1的区间[L,R],很好处理;ans=cal(R)-cal(L-1);cal(x)表示集合1到集合x,这x个集合一共加进去的数的个数;加入集合k的数,根据题目给的公式可以推导出就是2^lowbit(k),即2的整数次幂;所以直接枚举2的整数次幂即可在log(x)的时间复杂度里快速得出cal(x)答案对于询问2,先看一