做競賽題的人可能都有過這種體驗(yàn)看到 “區(qū)間修改 區(qū)間查詢” 的第一反應(yīng)就是上線段樹三分鐘敲完模板然后發(fā)現(xiàn)要么超時要么答案壓根不對。尤其是當(dāng)題目里混進(jìn) “構(gòu)造”“數(shù)學(xué)”“規(guī)律” 這些字眼時很多人就直接放棄了。我這幾年刷算法提高類的題最大的感受是真正把“線段樹 數(shù)學(xué)”這類硬核區(qū)間題做明白的人不是線段樹打得有多熟而是愿意在草稿紙上多推幾步公式。這篇文章想聊的就是那些“看似是數(shù)據(jù)結(jié)構(gòu)題實(shí)際靠數(shù)學(xué)救場”的區(qū)間問題。我會用幾個典型例子拆解推導(dǎo)過程把懶標(biāo)記怎么設(shè)計、勢能均攤怎么證明、公式校驗(yàn)為什么能判區(qū)間性質(zhì)一點(diǎn)一點(diǎn)講清楚。適合已經(jīng)會線段樹基本操作、但覺得進(jìn)階題無從下手的同學(xué)也適合正在備戰(zhàn)算法競賽或大廠算法筆試的人。你不需要一口氣讀完挑自己卡殼的章節(jié)看就行但如果你能把每道例子的推導(dǎo)親手寫一遍收獲會比看十篇教程都大。1. 別急著寫代碼先想清楚這題考的是數(shù)據(jù)結(jié)構(gòu)還是數(shù)學(xué)1.1 三類容易混淆的“區(qū)間題”區(qū)間問題在算法題里出現(xiàn)頻率很高但難度層級差別非常大。我一般把它們分成三類純數(shù)據(jù)結(jié)構(gòu)題操作和查詢都能直接翻譯成線段樹的節(jié)點(diǎn)維護(hù)、懶標(biāo)記合并。比如區(qū)間加、區(qū)間求和、區(qū)間最大值這類題考驗(yàn)的是模板熟練度。數(shù)據(jù)結(jié)構(gòu) 數(shù)學(xué)建模題操作本身有“不規(guī)則性”比如區(qū)間開根號、區(qū)間取模、區(qū)間加等差數(shù)列如果不做數(shù)學(xué)化處理線段樹的懶標(biāo)記根本沒法定義或者更新一次要動一片葉子。數(shù)學(xué)為主、數(shù)據(jù)結(jié)構(gòu)為輔的題比如“判斷一個區(qū)間能否重排成等差數(shù)列”“區(qū)間內(nèi)是否滿足某種模運(yùn)算規(guī)律”這類題核心是找到一組“特征值”用公式把特征值快速算出來線段樹只是幫你在 log 時間內(nèi)拿到這些特征值。很多人一上來就把第三類當(dāng)?shù)诙愖鰧懥艘粋€超級復(fù)雜的線段樹去維護(hù)“能不能重排成等差數(shù)列”這種 bool 標(biāo)記結(jié)果根本沒法合并。其實(shí)答案早在數(shù)學(xué)里能不能構(gòu)成等差數(shù)列不是靠搜索驗(yàn)證的是靠“必要條件足夠強(qiáng)”來判定的。這個思路的轉(zhuǎn)變才是解題的分水嶺。1.2 為什么數(shù)學(xué)性質(zhì)直接決定算法復(fù)雜度拿“區(qū)間開根號求和”來說。如果線段樹維護(hù)的是區(qū)間最大值我們可以發(fā)現(xiàn)一個關(guān)鍵事實(shí)任何一個大于 1 的數(shù)連續(xù)開整數(shù)次根號后很快就會變成 1而 1 再開根號還是 1。也就是說每個葉子節(jié)點(diǎn)真正需要“被更新”的次數(shù)是極少的。這樣我們就能設(shè)計一種“暴力但均攤后復(fù)雜度極低”的更新策略區(qū)間被完整覆蓋時如果最大值已經(jīng)等于 1直接跳過否則一路下鉆到葉子。單點(diǎn)更新的次數(shù)總和是 O(n log log MAX)再乘上樹高 log n總復(fù)雜度依然非?？捎^。這個例子里線段樹的結(jié)構(gòu)沒有變變的只是更新策略。而更新策略的依據(jù)就是從數(shù)學(xué)上證明了“勢能下降有界”。所以我一直認(rèn)為刷這類題的目的不是背更多模板而是鍛煉一種能力把每個修改操作翻譯成“某種量在有界次操作后必然收斂”的形式。掌握這個思路你看到很多看似無解的題都會打開新局面。2. 典例一區(qū)間開根求和的勢能分析2.1 樸素想法為什么不行題目模型是給定長度為 n 的數(shù)組支持兩種操作第一種把區(qū)間 [l, r] 內(nèi)每個數(shù)變成它的向下取整平方根第二種查詢區(qū)間和。數(shù)據(jù)范圍 n 和操作次數(shù)可能是 1e5數(shù)組元素在 1e18 以內(nèi)。最直觀的想法是線段樹每個節(jié)點(diǎn)維護(hù)區(qū)間和區(qū)間開根號時因?yàn)殚_根號不是區(qū)間加、區(qū)間乘這類“可打懶標(biāo)記”的操作只好一直遞歸到葉子對每個葉子單獨(dú)開根。這最壞情況下一次操作就是 O(n log n)如果來 1e5 次操作直接爆炸。那能不能用懶標(biāo)記存一個“開根若干次”的狀態(tài)也不行因?yàn)椴煌恢玫臄?shù)開根次數(shù)不一樣無法統(tǒng)一合并。所以必須換個角度找性質(zhì)。2.2 核心推導(dǎo)開根下降次數(shù)最多有多少次關(guān)鍵性質(zhì)其實(shí)很簡單對于任意整數(shù) x ≥ 2令 y floor(√x)則 y x且當(dāng) x 很大時y 大約只有 x 的一半位數(shù)。比如1e18 開根約等于 1e91e9 開根約等于 3162231622 開根約等于 177177 開根約等于 1313 開根約等于 33 開根約等于 1也就是說1e18 級別的數(shù)開根 6 次就掉到 1 了。全局來看每個葉子在它被真正更新的次數(shù)上都有一個非常小的上限 O(log log MAX)。那么即使我們每次區(qū)間更新時野蠻地下鉆到葉子所有葉子累積被訪問的次數(shù)也不會超過 n × log log MAX。這樣一來線段樹上每個內(nèi)部節(jié)點(diǎn)還能再剪一刀如果當(dāng)前節(jié)點(diǎn)的區(qū)間最大值已經(jīng)是 1說明這個區(qū)間內(nèi)所有數(shù)都已經(jīng)變 1不用再下鉆。于是總時間復(fù)雜度可以證明為 O((n q) log n log log MAX)實(shí)際操作中遠(yuǎn)遠(yuǎn)跑不滿。2.3 可參考的實(shí)現(xiàn)代碼#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; ll a[N], sumv[N 2], maxv[N 2]; void pull(int p) { sumv[p] sumv[p 1] sumv[p 1 | 1]; maxv[p] max(maxv[p 1], maxv[p 1 | 1]); } void build(int p, int l, int r) { if (l r) { sumv[p] maxv[p] a[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pull(p); } void update(int p, int l, int r, int ql, int qr) { if (ql l r qr maxv[p] 1) { // 整個區(qū)間內(nèi)全是 1開根號沒有任何變化 return; } if (l r) { maxv[p] (ll)sqrtl(maxv[p]); // 注意用 sqrtl 保證精度 sumv[p] maxv[p]; return; } int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr); pull(p); } ll query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return sumv[p]; int mid (l r) 1; ll res 0; if (ql mid) res query(p 1, l, mid, ql, qr); if (qr mid) res query(p 1 | 1, mid 1, r, ql, qr); return res; }注意sqrt 的浮點(diǎn)精度在很多編譯器里對 1e18 數(shù)量級會產(chǎn)生偏差競賽中我強(qiáng)烈建議用sqrtl或者用二分法手動開整數(shù)根。我因?yàn)檫@個精度問題踩過不止一次坑最后統(tǒng)一改成了sqrtl過題速度也沒慢多少。2.4 還能怎么遷移這個套路一旦理解了“勢能均攤”類似題目直接套區(qū)間取模維護(hù)區(qū)間最大值如果最大值小于當(dāng)前模數(shù)整個區(qū)間直接跳過否則下鉆到葉子。數(shù)學(xué)上可以證明每個數(shù)被有效取模的次數(shù)是 O(log x)因?yàn)?x % m ≤ x / 2當(dāng) m ≤ x / 2 時顯然當(dāng) m x / 2 時余數(shù)為 x - m x / 2。區(qū)間變約數(shù)個數(shù)比如把每個數(shù)變成它的約數(shù)個數(shù)也是每個點(diǎn)下降若干次后穩(wěn)定。這類題表面上是“區(qū)間暴力更新”但因?yàn)槊總€點(diǎn)的下降次數(shù)有對數(shù)級別的天花板整體復(fù)雜度就能被數(shù)學(xué)性質(zhì)兜住。3. 典例二區(qū)間能否重排成等差數(shù)列——公式校驗(yàn)法3.1 題目模型信息合并的難點(diǎn)再來看一道更符合標(biāo)題氣質(zhì)的題給定數(shù)組支持單點(diǎn)修改多次查詢區(qū)間 [l, r] 內(nèi)的數(shù)能否通過重排構(gòu)成一個等差數(shù)列通常還會加一個約束公差 d 是正整數(shù)或者允許 d 0。如果只靠線段樹存一個“這個區(qū)間已經(jīng)是等差數(shù)列”的布爾值合并兩個子區(qū)間時是沒法判斷的因?yàn)槟悴恢雷筮厖^(qū)間的最后一個數(shù)和右邊區(qū)間的第一個數(shù)是否銜接上了。直接維護(hù)區(qū)間排好序的完整列表更不可能合并代價太大。所以我們需要換一個思路不直接判斷序列本身而是用一組“必要條件”來把所有可能的情況卡死。3.2 推導(dǎo)過程四個特征值缺一不可假設(shè)區(qū)間長度為 len r - l 1如果這 len 個數(shù)可以重排成公差為 d 的等差數(shù)列那么設(shè)最小值為 mn最大值為 mx則若 len 1一定可以公差任意。若 len 2一定可以公差是 mx - mn大于等于 0 即可。若 len ≥ 3 且 d 0所有數(shù)必須相等也就是 mx mn。若 d 0必須滿足 (mx - mn) % (len - 1) 0并且公差 d (mx - mn) / (len - 1)。但僅僅滿足最大值和最小值的關(guān)系還不夠。比如區(qū)間是 {1, 2, 4, 5}mn1mx5len4(5-1) % 3 0d 4/3 并不是整數(shù)所以會被篩掉。再看 {1, 2, 3, 5}mn1mx5(5-1)%3 0 不成立也會被篩掉。但 {1, 2, 4, 7} 呢(7-1)%3 2也不行。真正嚴(yán)格的情形是 {1, 2, 4, 8}d 算出來不是整數(shù)所以仍不滿足。那有沒有可能 mn、mx 都滿足整除關(guān)系但區(qū)間里亂序例如 len4mn1mx7d2理論上數(shù)列是 {1, 3, 5, 7}但實(shí)際區(qū)間可能是 {1, 2, 5, 7}。這種情況只靠 min 和 max 檢測不出來所以還要加上和校驗(yàn)。等差數(shù)列的和公式是sum_true (mn mx) * len / 2如果區(qū)間實(shí)際和等于這個值范圍進(jìn)一步縮小。但還可能有構(gòu)造失效的情況{1, 3, 5, 7} 和 {1, 5, 5, 7}后者的和是 18前者和是 16不相等被排除。那有沒有區(qū)間和恰好等于理論值但又不是等差數(shù)列的有比如 {1, 2, 6, 7}mn1mx7len4理論和為 16實(shí)際和也是 16。肉眼可見它不是等差數(shù)列。所以和還不夠需要繼續(xù)加特征。此時用平方和校驗(yàn)sum_sq_true mn^2 (mnd)^2 ... (mx)^2推導(dǎo)公式可以寫成sum_sq_true (mn^2 mx^2) * len / 2 d^2 * (len - 1) * len / 6等等這個公式要仔細(xì)推。設(shè)數(shù)列元素為 a_i mn i * di 從 0 到 len-1。那么sum_sq_true Σ(mn i*d)^2 Σ(mn^2 2*mn*i*d i^2*d^2) len * mn^2 2 * mn * d * (len-1)*len/2 d^2 * (len-1)*len*(2*len-1)/6 len * mn^2 mn * d * len * (len-1) d^2 * len * (len-1) * (2*len-1) / 6如果你維護(hù)了區(qū)間和、平方和再配合 mn 和 mx就能把大部分非法情況排除。但這套必要條件在數(shù)學(xué)上并不是完全充分的因?yàn)榭赡艽嬖诠Ｅ鲎矊?shí)際競賽里為了簡化通常把平方和校驗(yàn)換成一組隨機(jī)權(quán)值的哈希校驗(yàn)比如對值域映射隨機(jī)大數(shù)后求和或者直接用兩個大質(zhì)數(shù)下的模運(yùn)算來降低碰撞概率。對于以“能否重排成等差數(shù)列”為判定目標(biāo)的題嚴(yán)格來說還需要判斷區(qū)間內(nèi)有沒有重復(fù)元素所以往往還會維護(hù)一個“值域上的出現(xiàn)次數(shù)哈希”?，F(xiàn)實(shí)中更常見的考法是題目改成“區(qū)間排序后是否等于某個等差數(shù)列的前若干項(xiàng)”這時候等價于驗(yàn)證集合相等用兩個哈?；蛘唠S機(jī)權(quán)值異或等方式做。線段樹節(jié)點(diǎn)里維護(hù)的就不再是單個和而是一組特征值。3.3 合并操作和代碼骨架為了簡潔這里用隨機(jī)權(quán)值哈希演示思路。給每個數(shù)值 x 分配一個 64 位隨機(jī)數(shù) h[x]線段樹節(jié)點(diǎn)維護(hù)區(qū)間最小值 mn區(qū)間最大值 mx區(qū)間隨機(jī)權(quán)值異或和 xr或者和區(qū)間實(shí)際和 sum便于校驗(yàn)等差數(shù)列求和公式每次合并兩個子區(qū)間mn 取小、mx 取大、xr 取異或、sum 直接相加。判斷一個區(qū)間能否構(gòu)成等差數(shù)列時先用 mn 和 mx 算出理論首項(xiàng)和公差再用等差序列的哈希公式計算出“理論區(qū)間哈?！弊詈蠛蛯?shí)際維護(hù)的 xr 比對。隨機(jī)權(quán)值下碰撞概率極低工程上可以接受。這個思路說明了一個很重要的點(diǎn)有些時候我們不需要維護(hù)“直接答案”而是維護(hù)一組可以被公式快速驗(yàn)證的特征值。這也解釋了為什么很多題解里線段樹節(jié)點(diǎn)會同時維護(hù)最大值、最小值、和、平方和因?yàn)槊總€特征都是來“逼近”最終判定條件的。注意如果題目明確要求判斷是否包含重復(fù)元素單純靠和、平方和、隨機(jī)哈希都不能完全解決重復(fù)元素問題。更可靠的辦法是額外維護(hù)每個數(shù)上次出現(xiàn)的位置然后用區(qū)間最大值判斷是否有重復(fù)這是另一套基于“前驅(qū)位置”的技巧這里就不展開了。4. 典例三區(qū)間加等差數(shù)列——一次函數(shù)懶標(biāo)記的推導(dǎo)與下傳4.1 操作模型與問題難點(diǎn)題目模型對區(qū)間 [l, r] 的每個位置 i加上一個首項(xiàng)為 A、公差為 D 的等差數(shù)列也就是a[i] A (i - l) * D同時支持查詢區(qū)間和。數(shù)據(jù)范圍照例是 1e5操作數(shù)量也是 1e5。如果我們給每個位置都單獨(dú)算首項(xiàng)顯然不能打統(tǒng)一懶標(biāo)記。但仔細(xì)觀察*這個更新本質(zhì)上是在區(qū)間上疊加一個一次函數(shù) f(i) A (i-l)D。也就是說更新到的每一個點(diǎn)其真實(shí)增量可以寫成關(guān)于位置 i 的線性函數(shù)。既然線段樹每個節(jié)點(diǎn)都對應(yīng)一個連續(xù)區(qū)間那我們就可以把懶標(biāo)記設(shè)計成“這個區(qū)間整體增加了一個一次函數(shù)”。4.2 標(biāo)記合并與下傳的公式推導(dǎo)設(shè)節(jié)點(diǎn) p 對應(yīng)區(qū)間 [l, r]當(dāng)前有一個待下傳的懶標(biāo)記表示區(qū)間內(nèi)每個位置 i 都要增加tag_val(i) k * i b這里的 k 對應(yīng)公差b 是常數(shù)項(xiàng)。注意這種寫法里位置 i 用的是全局下標(biāo)這樣好處是合并子區(qū)間時不需要換元。但實(shí)際操作中因?yàn)閎的值會隨區(qū)間左端點(diǎn)變化很多人容易把符號搞混。如果兩次懶標(biāo)記分別是 k1i b1 和 k2i b2疊加后顯然是(k1 k2) * i (b1 b2)所以懶標(biāo)記合并只需要兩個加法不用做任何乘除。這個結(jié)論對“ pushdown 到子節(jié)點(diǎn)”很重要當(dāng)一個節(jié)點(diǎn)把懶標(biāo)記傳給左孩子時左孩子區(qū)間 [l, mid] 的所有位置 i 同樣增加 k*i b所以直接加在孩子的 k 和 b 上即可傳給右孩子也不例外因?yàn)楣嚼镆呀?jīng)用了全局下標(biāo)右孩子區(qū)間 [mid1, r] 照樣套在圖里。但是要小心節(jié)點(diǎn)維護(hù)的區(qū)間和怎么更新假設(shè)當(dāng)前節(jié)點(diǎn)區(qū)間是 [l, r]長度 len r - l 1每個位置 i 增加 k*i b那么區(qū)間和增加Σ_{il}^{r} (k*i b) k * (l r) * len / 2 b * len這個公式在 update 和 pushdown 里都要用。稍有不注意左孩子更新后可能忘記把同樣是 k 的項(xiàng)帶進(jìn)去導(dǎo)致區(qū)間和算錯。4.3 可參考的實(shí)現(xiàn)代碼struct Node { ll sum; ll k; // 公差 ll b; // 一次函數(shù)常數(shù)項(xiàng) } tree[N 2]; ll calc_sum(int l, int r, ll k, ll b) { ll len r - l 1; return k * (l r) * len / 2 b * len; } void apply(int p, int l, int r, ll k, ll b) { tree[p].sum calc_sum(l, r, k, b); tree[p].k k; tree[p].b b; } void pushdown(int p, int l, int r) { if (tree[p].k 0 tree[p].b 0) return; int mid (l r) 1; apply(p 1, l, mid, tree[p].k, tree[p].b); apply(p 1 | 1, mid 1, r, tree[p].k, tree[p].b); tree[p].k tree[p].b 0; } void update(int p, int l, int r, int ql, int qr, ll A, ll D) { if (ql l r qr) { // 當(dāng)前區(qū)間整體加首項(xiàng) A公差 D // 由于公式基于全局下標(biāo)直接 apply(k D, b A - D * l) ll k D; ll b A - D * ql; // 注意這里是用 ql 推導(dǎo)不是用當(dāng)前節(jié)點(diǎn)的 l apply(p, l, r, k, b); return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) update(p 1, l, mid, ql, qr, A, D); if (qr mid) update(p 1 | 1, mid 1, r, ql, qr, A, D); tree[p].sum tree[p 1].sum tree[p 1 | 1].sum; }注意一個細(xì)節(jié)區(qū)間完全覆蓋時我直接用了b A - D * ql。為什么不是A - D * l因?yàn)轭}目定義A是區(qū)間左端點(diǎn) ql 位置的增量。對任意位置 i 而言實(shí)際增量為A (i - ql) * D D * i (A - D * ql)所以一次函數(shù)的常數(shù)項(xiàng)b必須基于真實(shí)的區(qū)間左端點(diǎn) ql 來算而不是基于當(dāng)前線段樹節(jié)點(diǎn)的 l。如果這里搞混更新區(qū)間不是恰好和節(jié)點(diǎn)區(qū)間重疊時就會產(chǎn)生系統(tǒng)性偏差。我當(dāng)時第一次寫就踩了這個坑查了半天才發(fā)現(xiàn)是 b 算錯了。4.4 為什么一次函數(shù)標(biāo)記很好用這個例子的意義在于很多看起來“不規(guī)則”的區(qū)間加法本質(zhì)都是某個低次多項(xiàng)式在區(qū)間上的疊加。一次函數(shù)是最簡單的如果題目變成區(qū)間加二次函數(shù)做法完全同理只是區(qū)間和的更新公式要從等差擴(kuò)展到平方和公式。這也正是“線段樹 數(shù)學(xué)”最核心的復(fù)利效應(yīng)你每多掌握一個公式就能多解鎖一類懶標(biāo)記設(shè)計。如果再配合后續(xù)的“二次函數(shù)前綴和”“調(diào)和級數(shù)預(yù)處理”你會發(fā)現(xiàn)許多題目都是同一個套路把修改操作映射為一個在位置上有閉式表達(dá)式的函數(shù)推一下節(jié)點(diǎn)信息更新的公式然后線段樹照常跑。5. 進(jìn)階方向動態(tài)開點(diǎn)線段樹與線段樹套線段樹5.1 什么時候需要動態(tài)開點(diǎn)做區(qū)間數(shù)學(xué)題時有時值域特別大比如 1e9而且不是所有位置都會用到。這時如果開一棵滿二叉樹內(nèi)存直接爆掉。動態(tài)開點(diǎn)線段樹的核心思想是用多少節(jié)點(diǎn)才建多少節(jié)點(diǎn)每個節(jié)點(diǎn)只有在被更新或查詢訪問到時才創(chuàng)建。記錄左右兒子的下標(biāo)編號而不是用p1、p1|1。這樣一次單點(diǎn)修改會新建 O(log V) 個節(jié)點(diǎn)V 是值域。區(qū)間加、區(qū)間求和的操作照常只是每個節(jié)點(diǎn)多了兩個 int 指針。struct Node { int lc, rc; ll sum, lazy; } tr[N * 40]; int tot 0, root 0; void pushup(int p) { tr[p].sum tr[tr[p].lc].sum tr[tr[p].rc].sum; } void modify(int p, int l, int r, int ql, int qr, ll val) { if (!p) p tot; if (ql l r qr) { tr[p].sum val * (r - l 1); tr[p].lazy val; return; } int mid (l r) 1; if (ql mid) modify(tr[p].lc, l, mid, ql, qr, val); if (qr mid) modify(tr[p].rc, mid 1, r, ql, qr, val); pushup(p); }注意modify的第一個參數(shù)是引用這是動態(tài)開點(diǎn)的關(guān)鍵因?yàn)樵谶f歸過程中可能會創(chuàng)建新節(jié)點(diǎn)必須把地址傳回去。5.2 線段樹套線段樹的邏輯框架樹套樹一般出現(xiàn)在二維統(tǒng)計題里比如平面 n 個點(diǎn)支持單點(diǎn)修改權(quán)值查詢矩形區(qū)間內(nèi)滿足某個數(shù)學(xué)條件的點(diǎn)的個數(shù)。之所以套樹是因?yàn)閱慰镁€段樹只能管一個維度要同時約束兩個維度就得內(nèi)外兩層索引。外層線段樹按 x 坐標(biāo)分治每個節(jié)點(diǎn)內(nèi)部再維護(hù)一棵動態(tài)開點(diǎn)的權(quán)值線段樹用于統(tǒng)計該 x 區(qū)間內(nèi)不同 y 的出現(xiàn)情況。修改一個點(diǎn) (x0, y0) 時外層從根走到葉子沿途每個節(jié)點(diǎn)都在它的內(nèi)層線段樹上對 y0 做一次單點(diǎn)更新復(fù)雜度 O(log n) × O(log C)C 是 y 值域。查詢矩形 [x1, x2] × [y1, y2] 時外層先找到所有覆蓋 x 區(qū)間的 O(log n) 個節(jié)點(diǎn)然后在每個節(jié)點(diǎn)的內(nèi)層線段樹上查詢 y 區(qū)間內(nèi)的和累加結(jié)果。代碼模板大概長這樣但完整較短版本如下struct InnerTree { int ls, rs, sum; }; void inner_update(int p, int l, int r, int pos, int val) { if (!p) p tot_inner; tr_inner[p].sum val; if (l r) return; int mid (l r) 1; if (pos mid) inner_update(tr_inner[p].ls, l, mid, pos, val); else inner_update(tr_inner[p].rs, mid 1, r, pos, val); } // 外層線段樹節(jié)點(diǎn)編號用 out[p] 指向 inner 的根 void outer_update(int p, int l, int r, int x, int y, int val) { inner_update(out[p], 1, MAX_Y, y, val); if (l r) return; int mid (l r) 1; if (x mid) outer_update(p 1, l, mid, x, y, val); else outer_update(p 1 | 1, mid 1, r, x, y, val); }用引用傳遞內(nèi)層根下標(biāo)時要注意out[p]本身是 int傳入inner_update(out[p], ...)時要確保它是一個可修改的左值否則 new 出來的節(jié)點(diǎn)會丟。5.3 什么時候該放棄樹套樹樹套樹的代碼量不小常數(shù)也大調(diào)試難度高。如果題目允許離線很多二維區(qū)間數(shù)學(xué)統(tǒng)計其實(shí)可以換成 CDQ 分治、樹狀數(shù)組套權(quán)值線段樹、莫隊二次離線等方案。我的個人經(jīng)驗(yàn)是如果只涉及單點(diǎn)修改、矩形查詢并且強(qiáng)制在線才考慮樹套樹。如果能離線優(yōu)先想 CDQ 分治 樹狀數(shù)組代碼更穩(wěn)。如果值域不大甚至可以二維前綴和的差分思路。不要因?yàn)闃?biāo)題里有“樹套樹模板”就去硬背。真正比賽時能用簡單方法解決就別給線段樹套線段樹加戲。6. 現(xiàn)場翻車實(shí)錄線段樹 數(shù)學(xué)題的常見坑6.1 懶標(biāo)記合并順序和覆蓋問題很多人寫區(qū)間加等差數(shù)列時把k和b分開傳但 pushdown 時沒有先把子節(jié)點(diǎn)的舊懶標(biāo)記算進(jìn) sum導(dǎo)致覆蓋了舊標(biāo)記。正確的做法是apply 時先更新 sum再疊加懶標(biāo)記不能先存標(biāo)記后更新 sum否則查詢時子節(jié)點(diǎn)沒有及時拿到上一層的增量。另外樹套樹的懶標(biāo)記在多層結(jié)構(gòu)里容易重復(fù)下傳建議每個節(jié)點(diǎn)都寫一個pushdown如果沒有懶標(biāo)記就立即返回。6.2 公式里的除法與取整等差數(shù)列求和公式和平方和公式里都有除以 2、除以 6如果直接len * (len - 1) / 2在 len 很大時先乘后除可能溢出 long long。穩(wěn)妥的辦法是先除以 2或者用__int128中間運(yùn)算。我見過很多次有人在這里爆負(fù)排查半天才發(fā)現(xiàn)是溢出?！?提示如果題目里所有數(shù)都是正數(shù)一旦線段樹的 sum 變成負(fù)數(shù)優(yōu)先懷疑溢出其次才是懶標(biāo)記寫錯。6.3 隨機(jī)哈希的穩(wěn)定性用隨機(jī)權(quán)值哈希做區(qū)間集合判定時碰撞概率和隨機(jī)數(shù)的質(zhì)量直接相關(guān)。我在本地用mt19937_64生成權(quán)值配合std::uniform_int_distributionunsigned long long實(shí)際跑下來非常穩(wěn)。但不要用rand()它的 16 位隨機(jī)數(shù)在哈希題里很容易被卡。還可以直接用兩個不同的模數(shù)做雙哈希雖然代碼更啰嗦但安全性更高。6.4 輸入輸出與卡常涉及 1e5 級別的操作cin/cout不關(guān)同步會拖累整體時間。我一般直接加ios::sync_with_stdio(false); cin.tie(nullptr);線段樹節(jié)點(diǎn)如果開了 struct盡量把sum, max, lazy, k, b這些字段按訪問頻率排序緩存友好一點(diǎn)。對于動態(tài)開點(diǎn)數(shù)組盡量開 4 倍之上不要用 vector 動態(tài)擴(kuò)容比賽環(huán)境里 vector 的擴(kuò)容開銷很致命。下面是我總結(jié)的快速排查表異常現(xiàn)象可能原因處理方式區(qū)間查詢結(jié)果偏小pushdown 沒有更新子節(jié)點(diǎn) sum在 pushdown 里先 apply 再清除懶標(biāo)記更新后區(qū)間和出現(xiàn)負(fù)數(shù)公式溢出中間過程用 __int128 或保證除法的先后順序樹套樹修改后數(shù)據(jù)丟失內(nèi)層根節(jié)點(diǎn)傳參失敗確保inner_update第一個參數(shù)是引用開根題在 1e18 數(shù)據(jù)下 WAsqrt 精度不足用sqrtl或手動二分整數(shù)根等差數(shù)列判定誤判最小值和最大值不滿足整除關(guān)系先檢查 (mx - mn) % (len - 1) 0哈希判斷偶爾 WA隨機(jī)權(quán)值碰撞或用了弱哈希換mt19937_64或改雙哈希6.5 數(shù)據(jù)對拍是最有效的調(diào)試方式線段樹 數(shù)學(xué)這類題推導(dǎo)一旦有誤樣例可能都能過但大數(shù)據(jù)一上就原形畢露。我每次都會寫一個小的暴力程序生成隨機(jī)數(shù)組和隨機(jī)操作然后和線段樹程序?qū)ε?。幾萬組數(shù)據(jù)跑下來只要有一組不一致就能定位到哪個操作出了問題再配合斷點(diǎn)看節(jié)點(diǎn)的 sum 和懶標(biāo)記基本十幾分鐘內(nèi)能找到 bug。對拍的代碼框架很簡單生成隨機(jī)操作序列分別跑暴力和線段樹逐一比較結(jié)果。很多新人覺得寫對拍麻煩但它在進(jìn)階題上的性價比真的高得離譜。一點(diǎn)個人經(jīng)驗(yàn)總結(jié)做了這么多線段樹 數(shù)學(xué)的題我最大的體會是題目越“硬核”越要做足紙面功夫。拿到一道題先不要想線段樹怎么寫而是先在草稿紙上把修改操作用數(shù)學(xué)語言表達(dá)出來。如果它是一次函數(shù)就推一次函數(shù)的合并公式如果它是開根號取模就證明一下勢能下降有界如果它是判斷區(qū)間性質(zhì)就找一組必要條件并驗(yàn)證充分性。公式推導(dǎo)一旦成立線段樹的結(jié)構(gòu)基本就是明牌照著模板填就行。如果你現(xiàn)在正在刷題我建議把今天講的三個典型例子的推導(dǎo)過程親手抄寫一遍區(qū)間開根、等差數(shù)列判定、區(qū)間加等差數(shù)列。抄完之后再合上題解重新實(shí)現(xiàn)一遍。這個過程雖然慢但比刷十道水題都有用。希望這篇內(nèi)容能讓你在遇到線段樹和數(shù)學(xué)碰撞的題目時不再頭皮發(fā)麻而是有一種“讓我來算算”的底氣。