解析·優(yōu)化 ZKW線段樹

德魯伊！大自然已經(jīng)聽命于我了！
死亡之翼長子奈法利安

ZKW天下第一！
摘自某群聊天記錄

ZKW線段樹，即非遞歸形式的線段樹，出自終極大犇ZKW的論文《統(tǒng)計(jì)的力量》。與普通的線段樹相比，ZKW線段樹由于是非遞歸形式，效率極高，代碼也極短，成為了OI比賽中極為實(shí)用的優(yōu)化算法之一。雖然ZKW線段樹無法處理有運(yùn)算優(yōu)先級(jí)的線段樹問題，但是在一般的問題上和常數(shù)偏大的問題上總能帶來極強(qiáng)的游戲體驗(yàn)。

ZKW線段樹的建樹

普通線段樹
       1
      / \
     2   3                     <---------------"弱小，可伶又無助"
    / \ 
   4   5

ZKW線段樹
         1
       /   \
     10     11                     <---------------"天下第一！"
    / \     / \
  100 101 110 111

那么接下來進(jìn)入我們的分析環(huán)節(jié)：小學(xué)生找規(guī)律。
通過觀察，我們可以發(fā)現(xiàn)：線段樹對(duì)應(yīng)葉子節(jié)點(diǎn)的下標(biāo)和原數(shù)組的下標(biāo)的差值是恒定的
事實(shí)上，這個(gè)值幾乎恒等于線段樹數(shù)組里葉子節(jié)點(diǎn)的數(shù)量。
事實(shí)上，該值num滿足：num=2^{[log_2(n+1)]}
于是我們可以先將線段樹建為一棵滿二叉樹，然后我們從葉子節(jié)點(diǎn)開始回溯即可。
定義

#define maxn 10000
int n,num;
int minv[maxn<<2];

其中，minv為線段樹數(shù)組，n為總節(jié)點(diǎn)數(shù)量，N即為上文提到的N。
那么完整的建樹代碼如下

inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(){
  scanf("%d", &n);
  N=ksm(2,log2(n+1));
  for(register int i=N+1;i<=N+n;i++)cin>>minv[i];
  for(register int i=N-1;i>=1;i--)minv[i]=minv[i<<1]+minv[i<<1|1];
}

ZKW線段樹的修改&查詢

單點(diǎn)修改與單點(diǎn)查詢

代碼量很少，背模板即可

單點(diǎn)更新
inline void update(int x,int k){
    for(register int i=x+N;i;i>>=1)tree[i]+=k;
}
區(qū)間(單點(diǎn))查詢
inline int query(int l,int r){
    int ans=0;
    for(l=N+l-1,r=N+r+1;s ^ r ^ 1;s>>=1,r>>=1){
        if(~s&1)ans+=tree[s ^ 1];
        if(r&1)ans+=tree[r ^ 1];
    }
    return ans;
}
ZKW線段樹單點(diǎn)操作
#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
int n,N;
int a[maxn];
int ansv[maxn<<2];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(int n){
  N=ksm(2,log2(n+1));
  for(register int i=N+1;i<=N+n;i++)ansv[i]=a[i];
  for(register int i=N-1;i>=1;i--)ansv[i]=ansv[i<<1]+ansv[i<<1|1];
}
inline void update(int x,int k){
    for(register int i=x+N;i;i>>=1)ansv[i]+=k;
}
inline int query(int l,int r){
    int ans=0;
    for(l=N+l-1,r=N+r+1;s ^ r ^ 1;s>>=1,r>>=1){
        if(~s&1)ans+=tree[s ^ 1];
        if(r&1)ans+=tree[r ^ 1];
    }
    return ans;
}

區(qū)間修改與區(qū)間查詢

與普通線段樹類似的，我們?cè)赯KW線段樹上也不能使用暴力的方式進(jìn)行區(qū)間修改。在ZKW線段樹上做暴力修改的復(fù)雜度甚至比普通線段樹更高。同時(shí)，在ZKW線段樹中我們仍然需要使用到lazy標(biāo)記。然而不同的是，在ZKW線段樹中我們會(huì)將lazy標(biāo)記永久固化，即永遠(yuǎn)不對(duì)標(biāo)記做pushdown操作。
我們假定現(xiàn)在指定了一個(gè)區(qū)間[l,r]，使得區(qū)間的每一個(gè)值全部加上k，并使得l=2,r=10。
當(dāng)l到了[2,2]節(jié)點(diǎn)時(shí)，顯然[3,3]節(jié)點(diǎn)需要被標(biāo)記上k，那么接下來我們走到的[2,3]、[0,3]節(jié)點(diǎn)都會(huì)被標(biāo)記上k*1，等我們到達(dá)[0,7]節(jié)點(diǎn)時(shí)，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5B4%2C7%5D" alt="[4,7]" mathimg="1">已經(jīng)被標(biāo)記了k，所以[0,7]節(jié)點(diǎn)的值要加上k*(1+4)=k*5，自然我們需要一個(gè)變量來存儲(chǔ)k的系數(shù)。
需要注意的是，這次的修改要上推到根節(jié)點(diǎn)

inline void update(int l,int r,int k) {
    int lNum=0,rNum=0,nNum=1;
    for(l=N+l-1,r=N+r+1;l ^ r ^ 1;l>>=1,r>>=1,nNum<<=1){
        ansv[l]+=k*lNum;
        ansv[r]+=k*rNum;
        if(~s&1){
            lazy[s ^ 1]+=k;
            ansv[s ^ 1]+=k*nNum;
            lNum += nNum;
        }
        if(t&1){
            lazy[t ^ 1]+=k;
            ansv[t ^ 1]+=k*nNum;
            rNum+=nNum;
        }
    }
    for(;l;l>>=1,r>>=1){
        ansv[l]+=k*lNum;
        ansv[r]+=k*rNum;
    }    
}

區(qū)間查詢的過程類似。

inline int query(int l, int r){
    int lNum=0,rNum=0,nNum=1;
    int ans=0;
    for(l=N+l-1,r=N+r+1;l ^ r ^ 1;l>>=1,r>>=1,nNum<<=1){
        if(lazy[l])ans+=lazy[l]*lNum;
        if(lazy[r])ans+=lazy[r]*rNum;
        if(~l&1){
            ans+=ansv[l ^ 1];
            lNum+=nNum;
        }
        if(r&1){
            ans+=ansv[r ^ 1];
            rNum+=nNum;
        }
    }
    for(;l;l>>=1,r>>=1) {
        ans+=lazy[l]*lNum;
        ans+=lazy[r]*rNum;
    }
    return ans;
}
線段樹區(qū)間操作代碼
#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
int n,N;
int a[maxn];
int ansv[maxn<<2],lazy[maxn<<2];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(int n){
  N=ksm(2,log2(n+1));
  for(register int i=N+1;i<=N+n;i++)ansv[i]=a[i];
  for(register int i=N-1;i>=1;i--)ansv[i]=ansv[i<<1]+ansv[i<<1|1];
}
inline void update(int l,int r,int k) {
    int lNum=0,rNum=0,nNum=1;
    for(l=N+l-1,r=N+r+1;l ^ r ^ 1;l>>=1,r>>=1,nNum<<=1){
        ansv[l]+=k*lNum;
        ansv[r]+=k*rNum;
        if(~l&1){
            lazy[l ^ 1]+=k;
            ansv[l ^ 1]+=k*nNum;
            lNum += nNum;
        }
        if(r&1){
            lazy[r ^ 1]+=k;
            ansv[r ^ 1]+=k*nNum;
            rNum+=nNum;
        }
    }
    for(;l;l>>=1,r>>=1){
        ansv[l]+=k*lNum;
        ansv[r]+=k*rNum;
    }    
}
inline int query(int l, int r){
    int lNum=0,rNum=0,nNum=1;
    int ans=0;
    for(l=N+l-1,r=N+r+1;l ^ r ^ 1;l>>=1,r>>=1,nNum<<=1){
        if(lazy[l])ans+=lazy[l]*lNum;
        if(lazy[r])ans+=lazy[r]*rNum;
        if(~l&1){
            ans+=ansv[l ^ 1];
            lNum+=nNum;
        }
        if(r&1){
            ans+=ansv[r ^ 1];
            rNum+=nNum;
        }
    }
    for(;l;l>>=1,r>>=1) {
        ans+=lazy[l]*lNum;
        ans+=lazy[r]*rNum;
    }
    return ans;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容