树状数组新思考-学习笔记

高考后的第一篇博客... [Inspired by this](https://www.luogu.com.cn/blog/countercurrent-time/qian-tan-shu-zhuang-shuo-zu-you-hua) ## 树状数组$O(n)$建树。 ```cpp for(int i=1;i<=n;i++){ cin>>a[i]; if(i+lowbit(i)<=n) a[i+lowbit(i)]+=a[i];//注意这里的条件 } ``` 不常用的填表法 ```cpp for(int i=1;i<=n;i++) { cin>>a[i]; for(int j=1;j<lowbit(i);j<<=1){ a[i]+=a[i-j]; } } ``` ## 树状数组上二分 [from](https://www.luogu.com.cn/blog/Chanis/super-BIT2) 这里用到了倍增算法， 当我们把c[i]的下标加上2^k后，c[i+2^k]的值就是我们增加的这一段区间元素的个数。就可以直接判断当前元素个数是否超过了K，超过了就退回去，否则就保存。 ```cpp int findKth(int k){ int ans=0,cnt=0; for(int i=30;i>=0;i--){//i实际上为log2(maxn),maxn是a数组中的最大值 ans+=(1<<i); if(ans>maxn || cnt+c[ans]>=k)ans-=(1<<i);//>=k是为了防止有重复元素 else cnt+=c[ans]; } return ++ans;//如果找不到则返回n+1 } ``` ## 树状数组延迟标记 ## 树状数组可持久化