树状数组(待补订)
\(emm……\),作为一个完全可以被线段树代替的数据结构,其主要优点只有代码短与常数小
然而总有无聊的出题人卡常以及类似我的蒟蒻调不出线段树,所以还是得学一下的
树状数组天然用来维护前缀和,所以支持区间修改,单点查询;单点修改,区间查询
如果非要区间修改,区间修改也不是不行:
首先差分,令 \(d_i=a_i-a_{i-1}\)
\(S_i=\sum_{j=1}^{i}a_j\)
\(=\sum_{j=1}^i d_j(i-j+1)\)
\(=(i+1)\sum_{j=1}^{i}d_j-\sum_{j=1}^{i}jd_j\)
然后开两个树状数组维护 \(d_j\) 和 \(jd_j\) 即可
对于二维树状数组,直接开二维即可
注意内层循环的 \(y\) 不能直接用传进来的参数,应该每次循环都重新定义
关于树状数组上的二分,抄袭 \(cyh\) 代码(附赠改良码风服务)
int kth(int k){ // 查询第k大
int x=0;
for(int i=log2(n);i>=0;i--){
if(xc[x+(1<
P1972 [SDOI2009]HH的项链
还是一个比较常见的套路
即对于询问按右端点排序,然后贪心地对每个颜色选择一个“代表”,即最靠右的位置
那么每出现一个颜色,就在树状数组上 \(last[a[i]]\) 的位置上消除贡献
分块套树状数组
相当于是一个二维树状数组,只不过把第一维开在了块上,这样就可以在时空复杂度正确的情况下维护信息了
但是注意此时复杂度的保证是点是离散的,保证一个横坐标对应的点不会很多,这样零散块才可以很方便地暴力
复杂度好像比较神奇,是 \(O(\sqrt n+log^2n)\),但是在许多情境下运行效率大大优于树套树
CF1093E Intersection of Permutations
可以发现这道题的点是一个排列,于是满足了使用条件
注意由于树状数组是前缀和型的,因此询问应当拆分成容斥形式
树状数组套主席树
可以用于求解区间第 \(k\) 大,如果不需离散化可以在线进行
类似于线段树套平衡树,只不过把线段树替换为更快的树状数组,而平衡树+二分的过程变为了权值线段树上的二分
只需要记录出这一过程中树状数组上所有树根是什么,线段树的二分工作判断时应当统计当前所有树根的信息然后进行判断,
时间复杂度为 \(log^2n\),效率较高