[數據結構]走近Zkw線段樹（一）

01-28

0x00 Preface

說到線段樹大家都不陌生，一個用於維護區間信息的 $nlogn$ 數據結構。Zkw線段樹是一個改良版的線段樹。其功能與傳統線段樹相同，也是用於維護區間信息。但是Zkw線段樹有很多優點：1. 代碼簡短；2. 純天然非遞歸；3. 常數小（尤其在差分區間更新時），因此受到很多競賽黨的喜愛。由於涉及內容較多，Zkw線段樹將(預計)分兩篇文章介紹。本篇文章主要focus on zkw線段樹的原理 / 基礎功能。

P.S. 如果您想學線段樹可又無法完全理解那麼這篇文章十分適合您學習一個更加簡單的線段樹實現

0x01 Basis

為了輔助大家理解Zkw線段樹，我們先看一下傳統線段樹是如何存儲信息 / 建樹的：

不難看出，第 $i$ 個結點存儲的信息是第 $lfloor frac{i}{2} rfloor$ 個結點的前半段或後半段，並且葉子結點都是單點數據。傳統建樹的方法：

從根(當前)結點開始遞歸
如果 $l ne r$ 那麼存下當前端點信息，然後分別遞歸進入左子樹和右子樹；否則存下當前端點信息並輸入當前結點信息，退出當前遞歸。
維護當前結點 $i$ 的信息（即從左兒子和右兒子收集信息，如果是求和就把兩個結點值相加賦給父結點）

Talk is not that helpful ... 這裡是普通線段樹的建樹代碼:

inline void Maintain(int rt) {n // 這裡以區間和為例n tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;n}nvoid Build(int rt, int l,int r) {n tree[rt].l = l;n tree[rt].r = r;n // l==r -> 到達葉子結點n if(l == r) {n tree[rt].sum = read(); // 讀入數據n return;n }n int mid = (l+r) >> 1; // 求出l,r的中點n Build(rt<<1, l, mid); // 建立左區間(兒子)n Build(rt<<1|1, mid+1, r); // 建立右區間(兒子)n Maintain(rt); // 收集兒子們的信息給爹地n}n

說了這麼多，一句話總結：普通線段樹是自頂向下一直到葉子（信息輸入）然後在一層一層退回到根結點（信息收集）。那麼就有一位大神這麼問：「既然可以從頂向下，那麼能不能自底向上呢？」。答案是「完全O吉拔K」。因此誕生了Zkw線段樹（麻吉亞巴庫內）。

Zkw線段樹建樹的方式就是首先輸入葉子結點的信息然後再一路向上傳遞信息，直到根結點。這時問題又來了....Where is the first leaf？？？我怎麼找到第一個葉子在哪？假設我們的單點數量（葉子數量）正好是 $2^k$ ，那麼我們手裡就握著一個滿二叉樹了，這樣我們就能輕鬆地計算出來第一個結點的位置是： $2^{k}$ 。但是如果不是滿二叉樹怎麼辦呢？沒有關係，現在的電腦內存不是問題！直接開成滿二叉樹就好啦~~。這樣一來，第一個葉子結點的位置就是： $2^k+1(k=lceillog_2Nrceil)$ (見代碼下的解釋)，也就是比 $N$ 大的最小的 $2^k$ 。找到葉子結點之後，直接輸入葉子結點信息，然後一個一個結點上傳信息到父親結點。於是我們得到了這樣的代碼：

inline void Maintain(int x) {n tree[x] = tree[lson(x)] + tree[rson(x)];n}nninline void Build() {n for(M=1;M<N;M<<=1);n for(int i=M+1;i<=M+N;++i) scanf("%d", &tree[i]);n for(int i=M-1;i;--i) Maintain(i);n}n

Update on 10.06:

感謝 @Dilthey提示。

NOTICE：看到評論中很多朋友問為什麼要在 $M+1$ 處開始輸入。我這裡統一解釋一下，評論中我所說的也有問題(這裡說聲抱歉，昨天一天都在路上，沒有時間思考....)，以文章此處為標準好啦。

建議先看完下一節（區間和計算）再來看此處有助於理解。從 $M+1$ 開始是為了進行區間查詢。

假設我們查詢的區間就是 $[1,N]$ ，這時為了進行查詢我們會將 $[1,N]$ 轉換為 $(0,N-1)$ ，看上去沒有區別，其實是有區別的。由於位於 $0$ 上的數字是否能被統計上與左端點位置相關（ $L=M+1-1=M$ ），如果從 $M$ 開始輸入會導致查詢時統計不到位於 $0$ 上的信息，因為 $L$ 初始位置就是第一個葉子的位置了( $L=M$ )... 但是如果換成 $M+1$ 開始，查詢時 $L$ 的位置依舊是 $L=M+1-1=M$ ，但是第一個葉子的位置在 $M+1$ 上，這樣就能夠統計到那個葉子上的信息啦。因此要從 $M+1$ 開始輸入信息。

這樣一來，代碼一下縮短了好多！三行建樹，就是這麼簡潔。連左右兒子的位置也不需要存了呢~是不是美滋滋(不是，因為空間複雜度變高了好多....TAT不過萌大奶！內存這麼大！（滑稽)

0x02 Single-Point Modification

由於區間修改有一些不同的操作，本篇先介紹最簡單的單點修改。

由於單點修改僅需要修改葉子結點，因此Zkw線段樹的單點更新比傳統線段樹高到不知.....咳咳，非常簡單。由於我們能夠通過簡單的加法計算找到葉子結點，我們只需要(Simply)修改掉葉子結點的值，然後一路向上，更新到根結點。例如：如果修改了上圖 $[2,2]$ 的值，我們的更新路徑為：

（Graphviz用得不好不會畫這樣的....手繪了2333）

是不是很森破？代碼醬在這裡喲：

inline void Update(int pos,int v) {n pos += M;n tree[pos] = v;n for(pos>>=1;pos;pos>>=1) Maintain(pos);n}n

短，真短，真雞鵝短！非常輕鬆愉快地完成了Update操作。並且Zkw線段樹在Update上的效率要比普通線段樹優秀，因為Zkw線段樹尋找葉子的複雜度是 $O(1)$ ，Removed(而傳統線段樹是 $O(logN)$ 。所以如果某個題有頻繁的單點修改，Zkw線段樹會是一個非常好的選擇。)

感謝 @Schureed 提供的信息：事實上傳統線段樹在建樹時可以記錄下葉子結點位置，因此也可以做到 $O(1)$ 的葉子查找。

0x03 Range Sum Query

在僅存在單點更新的情況下，RMQ和區間和查詢方法一樣，因此這裡依舊以區間和查詢為例介紹區間操作。

當遇到區間和查詢時，問題雙來了....傳統線段樹通過遞歸查詢需要加和的區間最後統計所有的和，但是Zkw線段樹....沒法從頂上找到需要加和的區間啊QwQ....怎麼辦呢？但是換個方向思考...從底向上，查詢區間為 $[L,R]$ ，我們只能知道當前區間是否在查詢區間內，即：如果當前查詢區間左端點 $L$ 所指向結點是線段樹某個結點的左兒子且 $R-1 ne L$ (即右端點指向結點不是左端點指向結點的兄弟)，那麼它的兄弟結點 $L+1$ 必然在查詢區間內。同理，如果 $R$ 所指向結點的兄弟結點不是 $L$ ，那麼它的兄弟結點必然包含在查詢區間內。如圖：

因此我們實際能夠查詢到的是 $(L,R)$ 。沒有關係，我們只需要查詢 $(L-1, R+1)$ 那麼就相當於查詢 $[L, R]$ 啦~~多麼智慧。

為了避免重複查詢，當 $L$ 和 $R$ 是兄弟結點時，我們就需要停止統計啦。代碼如下。那麼區間和查詢的代碼如下：

inline int Sum(int l,int r) {n int ans = 0;n // l=l+M-1->將查詢區間改為L-1，r=r+M+1->將查詢區間改為R+1n // l^r^1 -> 相當於判斷l與r是否是兄弟節點n for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1) {n if(~l&1) // l % 2 == 0 即l是l/2的左兒子n ans += tree[l^1];n if(r&1) // r % 2 == 1 即r是r/2的右兒子n ans += tree[r^1];n }n return ans;n}n

Very Very森破，容易理解對不對？QwQ。人類的智慧！！Zkw大神的智慧！！Orz

這樣我們就能在非常短的篇幅內寫出一個優秀的線段樹啦~Zkw線段樹（一）至此結束啦。

0x04 後記

由於AP作業有點多，第二部分可能過一段時間才能更新...希望這篇文章能夠幫助您further理解線段樹的工作方法以及Zkw線段樹的工作原理。另外，Fedora的中文輸入法並不非常好使，如果粗線措自請告素沃亞~(這條除外2333)