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