zkw线段树

donotctjuntilAFO · 2023-04-30 14:47:09 · 算法·理论

前言

zkw线段树在无标记优先级问题的情况下，可以在更小常数和更小码量完成线段树的操作。

正文

众所周知，线段树码量大，常数也大，如何优化？

考虑观察特殊线段树的性质发现，如果这可线段树是棵满二叉树，那么节点 i 在线段树上的编号就是 i+n 。于是我们可以把线段树补成二的幂。之后操作变得很简单。

建树：

for(L=1;L<=n+1;L<<=1);
f(i,1,n)
    read(t[i+L]);
F(i,L-1,1)
    t[i]=t[i<<1]+t[i<<1|1];

单点加：

void update(int p,int v){for(p+=L;p;p>>=1)t[p]+=v;}

前缀查询：

int query(int i){
    int ans=0;
    for(i+=L+1;i;i>>=1)
        ans+=(i&1)*t[i^1];
    return ans;
}

后缀查询：

int query(int i){
    int ans=0;
    for(i+=L-1;i;i>>=1)
        ans+=!(i&1)*t[i^1];
    return ans;
}

区间查询：

int query(int l,int r){
    int ans=0;
    for(l+=L-1,r+=L+1;l^r^1;l>>=1,r>>=1)
        ans+=!(l&1)*t[l^1]+(r&1)*t[r^1];
    return ans;
}

我们发现，依然不能区间修改，但是我们可以采用标记永久化的思想，区间修改时打标记，区间查询时把标记加上去。

区间加：

void update(int l,int r,int v){
    int ln=0,rn=0,len=1;
    for(l+=p-1,r+=p+1;l^r^1;l>>=1,r>>=1,len<<=1){
        tree[l].sum+=v*ln;
        tree[r].sum+=v*rn;
        if(!(l&1)){
            tree[l^1].tag+=v;
            tree[l^1].sum+=v*len;
            ln+=len;
        }
        if(r&1){
            tree[r^1].tag+=v;
            tree[r^1].sum+=v*len;
            rn+=len;
        }
    }
    while(l){
        tree[l].sum+=v*ln;
        tree[r].sum+=v*rn; 
        l>>=1,r>>=1;
    }
}

区间查询:

int query(int l,int r){
    int ans=0,ln=0,rn=0,len=1;
    for(l+=p-1,r+=p+1;l^r^1;l>>=1,r>>=1,len<<=1){
        if(tree[l].tag)
            ans+=tree[l].tag*ln;
        if(tree[r].tag)
            ans+=tree[r].tag*rn;
        if(!(l&1)){
            ans+=tree[l^1].sum;
            ln+=len;
        }
        if(r&1){
            ans+=tree[r^1].sum;
            rn+=len;
        }
    }
    while(l){
        ans+=tree[l].tag*ln;
        ans+=tree[r].tag*rn; 
        l>>=1,r>>=1;
    }
    return ans;
}

等等。这样感觉还不如普通线段树了。

不过，如果只有区间加，单点查询的话。

使用标记永久化后：

void update(int l,int r,int v){
    for(l+=L-1,r+=L+1;l^r^1;l>>=1,r>>=1)
        t[l^1]+=!(l&1)*v,t[r^1]+=(r&1)*v; 
}
int query(int i){
    int ans=0;
    for(i+=L;i;i>>=1)
        ans+=t[i];
    return ans;
}