前言

我們都知道動態(tài)開點權值線段樹的空間復雜度是 ?的，但是很多題目中這樣的空間是會被卡的，那我們能不能優(yōu)化呢？

實現(xiàn)

看看下面這一棵樹：

在上圖中，紅色節(jié)點使我們平常會開的點。

但是我們發(fā)現(xiàn)，其實只要維護綠色的點和紅色的葉子結點。

其實，綠色節(jié)點就是所有葉子結點的虛樹。

然后我們考慮如何維護虛樹。

LCA

最基礎的操作，目的是求解兩個區(qū)間在線段樹上的 LCA。

首先不難發(fā)現(xiàn)，兩個區(qū)間的 LCA 等價于兩個區(qū)間中任意取兩點的 LCA，因為：

所以問題轉化成求兩個點的 LCA。

我們考慮記錄下每個節(jié)點的編號，然后通過異或完求最低位的 ?的方式求出 LCA 的深度，然后記錄下 LCA 右端點的編號。

在回收節(jié)點的時候可以釋放儲存右端點編號的空間，但是這里為了方便就不這樣做了。

注意到這里記錄右端點的編號可能會帶來一定的空間常數(shù)，所以還有一種時間 ?但是空間常數(shù)小的寫法：

ADD

目的是單點修改，考慮在線段樹上便利，根據(jù)節(jié)點情況的不同大力分類討論，建出新點與原來某個節(jié)點的 LCA。

QUERY

查詢區(qū)間和，這一部分與普通線段樹無異。

KTH

查詢第 ?大，用來作為線段樹上二分的一個模板，與普通線段樹也無異。

MERGE

合并兩棵線段樹，這一部分需要根據(jù)合并的兩棵線段樹所管轄的區(qū)間來決定是否需要新建節(jié)點或者更改所管轄的區(qū)間來保證虛樹上只存在葉子結點的 LCA 一性質(zhì)。

SPLIT

這一部分需要遞歸不斷處理，將一棵子樹的左右兒子拆開再合并。

MAINTAIN

再前面的操作中會使一棵子樹的根節(jié)點不斷變化，但是我們插入查詢時為了方便需要保證根節(jié)點管轄的區(qū)間是 ，所以需要此函數(shù)強制定義一個根節(jié)點。

代碼整合

以下是【模板】線段樹分裂的代碼：

復雜度

空間復雜度 ，可以證明，有 ?個葉子節(jié)點的虛樹最多只有 ?個節(jié)點，時間復雜度與正常線段樹一致，是 ?的。

總結

如果您是巨佬的話一定可以看出來這樣子構造出來的線段樹和壓縮 01Trie 在結構上大差不差，因此您也可以把它看作是壓縮 01Trie 的一種變體實現(xiàn)。