历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

神奇的zkw线段树

作者：

lixiaoqian_qwq , 2022-09-11 11:11:15 , 所有人可见 , 阅读 707

6

5

好久没发题解和分享了qwq

你有没有被一些毒瘤数据结构题卡到自闭？

是不是每次调线段树都要1h+？

这是每个oier心中的痛调试线段树的难度不亚于dfs！

而现在一种全新的数据结构横空出世

它由清华姚班大佬张昆纬设计

同时是一套可以吊打传统线段树的数据结构也将位运算发挥到了极致

那么来看看吧！

1. 先看看传统线段树有哪些缺点

码量大
虽然理论上使用了堆式存储但是每个节点实际维护的左右界限并不明显以至于线段树里还需要额外维护左右端点的信息
递归的线段树集中处理信息不方便这是一个很难解决的问题

2. zkw线段树是如何应对这些问题的

zkw在此时注意到了一个线段树的一个极端情况：叶子节点排满此时线段树为完全二叉树叶子节点为2的次幂
注意到完全二叉树有如下性质：
1. 假如完全二叉树中的节点不是叶子节点那么它必定有左儿子与右儿子各一个;
2. 对于节点u而言它一定有一个兄弟节点编号为 $u \oplus 1$

这些性质都是十分优秀的

因此我们需要构造一棵完全二叉树此时才能把线段树发挥到极致
然而数据不会保证需要维护的数组长度即叶子节点数量为2的次幂
既然这样我们可以将数组强行拉到2的次幂的长度！
即为：

int M ; // M为二叉树实际需要的叶子节点个数
for(M=1;M<=n+2;M<<=1) ; // 至于为什么要用n+2 这是后话

3. zkw线段树面对区间查询时是如何做的

我们以区间加法为例
如果需要查询 $[l,r]$ 这个区间可以先把它转化为一个开区间 $(l-1,r+1)$
接着 zkw线段树面临的问题就是如何将一个 $(l-1,r+1)$ 转化为若干个线段树维护节点的区间加法
先考虑左端点l
如果l为父节点的右儿子那么不用先把他加入答案因为他是开区间的左端点答案并不考虑这一个点
如果l为父节点的左儿子那么需要将他的兄弟即 $l \oplus 1$ 加入答案
右端点r同理
因此可以实现如下的代码（注意变成叶子节点时必须要加上 $M$ ！）：

inline int query(int l,int r)
{
    int ans=0 ;
    for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) ans+=tr[l^1] ; // l为偶数 此时l为父节点的左儿子
        if( r&1) ans+=tr[r^1] ; // r为奇数 此时r为父节点的右儿子
    }
    return ans ;
}

同时我们以区间加法为例完善一下最开始的建树代码：

inline void build(int n)
{
    for(M=1;M<=n;M<<=1) ;
    for(int i=1;i<=n;i++) tr[i+M]=arr[i] ; // 为了转化为开区间时能保证l不为负数
    for(int i=M-1;i;i--) tr[i]=tr[i<<1]+tr[i<<1|1] ; //这是传统线段树的一个pushup
}

4. zkw线段树是如何实现区间修改的

区间修改是传统线段树与st表和树状数组拉开差距的地方然而懒标记在传统线段树中实现起来十分复杂代码量会暴增
zkw线段树面临着同样的问题因此zkw线段树选择了使用标记永久化的方法
与区间查询类似 zkw线段树在区间覆盖到的节点上打上标记表示这棵子树中每个节点都要修改然而我们还需要更新祖先节点因为下层的修改确实波及到了线段树的上层

inline void add(int l,int r,int v)
{
    int len=1,cntl=0,cntr=0 ;  // cntl和cntr分别表示左右实际修改的区间总长度 
    for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1,len<<=1)
    {
        tr[l]+=cntl*v,tr[r]+=cntr*v ;
        if(~l&1) tr[l^1]+=v*len,mark[l^1]+=v,cntl+=len ;
        if( r&1) tr[r^1]+=v*len,mark[r^1]+=v,cntr+=len ;
    }
    while(l) tr[l]+=cntl*v,tr[r]+=cntr*v,l>>=1,r>>=1 ;
}

区间修改也会影响到区间查询因此同样地区间查询也要一直推到最上面

inline int query(int l,int r)
{
    int ans=0,len=1,cntl=0,cntr=0 ; // cntl和cntr分别表示左右实际修改的区间总长度
    for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1,len<<=1)
    {
        ans+=cntl*mark[l]+cntr*mark[r] ;
        if(~l&1) ans+=tr[l^1],cntl+=len ;
        if( r&1) ans+=tr[r^1],cntr+=len ;
    }
    while(l) ans+=cntl*mark[l]+cntr*mark[r],l>>=1,r>>=1 ;
    return ans ;
}