树状数组线性初始化学习笔记

树状数组回顾

  • 考虑一个区间[1,x],对于x,我们将其二进制展开成x=2^{i_1}+2^{i_2}+2^{i_3}+\cdots +2^{i_m},设i_1>i_2>\cdots >i_m,所以我们可以把这个区间分成O(log x)个小区间,长度分别为2^{i_1}([1,2^{i_1}]),2^{i_2}([2^{i_1}+1,2^{i_1}+2^{i_2}])等等,仔细观察可以发现这些小区间的共同特点都是如果区间结尾是R,那么区间长度就等于R二进制下最小的2的次幂即lowbit(R)
  • 基于以上的理论我们可以建立一个数组c,其中c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和,我们如果知道这个数组的信息的话那么就能在O(logn)的时间内求出[1,x]的前缀和,每次x-=lowbit(x)就可以了。事实上,这个数组还构成了一个树形结构,具体长啥样可以百度或者谷歌搜索一下,很多。
  • 性质:
    • 每个内部节点c[x]保存以它为根的子树中所有叶子节点的和;
    • 每个内部节点c[x]的子节点数等于lowbit(x)的位数;
    • 除树根外,每个内部节点c[x]的父节点是c[x+lowbit(x)](找第一个能覆盖它这个自区间的父节点);
    • 树的深度为O(logn)
  • 因为第三条的性质,保证了我们单点修改的复杂度是O(logn),因为包含了这个位置的所有c[x]就只有O(logn)个了。
  • 支持什么操作:
    • 单点修改,区间查询
    • 区间修改,单点查询(主要思想是树状数组动态维护a[i]的差分数组,区间修改就相当于更新差分标记,所以前缀和就是a[x]的单点值)
    • 还有一些其他操作比如区间修改区间查询,没学,因为觉得不如直接上线段树了,比较无脑而且正确率高一些。

正题:初始化

  • 考虑暴力构造c[x]数组就是对于每个位置a[i]进行一次单点修改,一共进行n次操作,时间复杂度即为O(nlogn)
  • 但是,考虑到树状数组的本质,我们知道一个c[x]管辖的是[x-lowbit(x)+1,x]中所有数的和,所以我们可以对a[i]求一个前缀和,求前缀和的时候更新c[x]数组,即c[x]=pre[x]-pre[x-lowbit(x)],这样就能线性构造了,时间复杂度O(n)
  • 代码:
int a[N],pre[N],sum[N];
inline int lowbit(int x){return x&(-x)}
void add(int x,int val){for(;x<=n;x+=lowbit(x))sum[x]+=val;}
int get(int x){
    int res=0;
    for (;x>0;x-=lowbit(x)) res+=sum[x];
    return res;
}
void init(){//线性构造
    for (int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
        sum[i]=pre[i]-pre[i-lowbit(i)];
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注