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

本文主要是介绍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,先看一下以下几点：1）
当i为2的整数次幂，C[i]记录的是A[1]到A[i]的前i项和2）
C[i]记录的是A[i-lowbit(i)+1]到A[i]的lowbit(i)项和，第1个特点就是其中一个特例8前面的数1到7在进行，i+=lowbit(i)过程中都会到达8,这之后i+=lowbit(i) 相当于就不断乘2；[9,11]区间里的数i+=lowbit(i)也会先到达12，再16,之后i+=lowbit(i) 也是相当于不断乘2；这样C[i]有另一种理解方式,记录的是A[k+1]到A[i]的和,其中k表示i之前lowbit(k)大于lowbit(i)的最大值；对于C[12]来说k就是8；  对于C[14]来说k就是123）
有了第2点作为基础，要记录A数组的前i项和只需要
int answer=0;
while(i>0)
{answer+=C[i];i-=lowbit(i);
}
return answer;
4）
对于i和i+lowbit(i)之间的数(不包括这两个本身)m,lowbit(m)必定小于lowbit(i)
并且,假设C[m]记录的是区间[L,R]的所有A[ ]值和,那么必有i<L<=R<i+lowbit
5）
有了第4点的基础
对于A[k]，它的值被哪些C[i]加进去了
可以这么写
int i=k;
while(i<=N)
{sum++;i=i+lowbit(i);//对于这些i,C[i]包括A[k]
}

LL cal(LL x)
{LL ans=0;for(LL i=0;(1LL<<i)<=x;++i)ans+=(x/(1LL<<i)-x/(1LL<<(i+1)))*(1LL<<i);return ans;
}
int main()
{LL n,q,ans,x,L,R;while(~scanf("%lld%lld",&n,&q)){int ob;while(q--){ans=0;scanf("%d",&ob);if(ob==1){scanf("%lld%lld",&L,&R);ans=cal(R)-cal(L-1);}else{scanf("%lld",&x);while(x<=n){ans++;x+=lowbit(x);}}printf("%lld\n",ans);}}return 0;
}

这篇关于hdu 5975 树状数组原理题(16亚洲区域赛大连站)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---