1. 問題引入從“123”數(shù)列到前綴和難題很多朋友在準(zhǔn)備算法競(jìng)賽比如藍(lán)橋杯時(shí)都會(huì)遇到一類題目題目描述看起來很簡(jiǎn)單甚至有點(diǎn)“幼稚”但數(shù)據(jù)范圍一出來直接讓人頭皮發(fā)麻。2021年藍(lán)橋杯C/C B組的這道F題“123”就是典型代表。乍一看它不就是生成一個(gè)“1, 1,2, 1,2,3, ...”的數(shù)列嗎求個(gè)區(qū)間和能有多難但當(dāng)你看到數(shù)據(jù)范圍——查詢次數(shù)T最多 10^6區(qū)間[l, r]的端點(diǎn)值最大能到 10^12 這個(gè)量級(jí)——你就知道暴力模擬生成數(shù)列再求和的路子走不通了。這道題的精髓在于它完美地考察了選手將具體問題抽象為數(shù)學(xué)模型并利用數(shù)學(xué)工具進(jìn)行高效計(jì)算的能力。它不是一個(gè)簡(jiǎn)單的編程題而是一個(gè)披著數(shù)列外衣的“數(shù)學(xué)前綴和二分查找”的綜合應(yīng)用題。如果你只是按部就班地循環(huán)生成數(shù)字那么程序在巨大的數(shù)據(jù)面前會(huì)立刻超時(shí)。我們必須找到數(shù)列背后隱藏的規(guī)律并設(shè)計(jì)出能在常數(shù)或?qū)?shù)時(shí)間內(nèi)回答每次查詢的算法。簡(jiǎn)單來說題目定義的數(shù)列是這樣的首先有一個(gè)無限長(zhǎng)的序列S它由無數(shù)個(gè)從1開始遞增的連續(xù)正整數(shù)段拼接而成。第一段是[1]第二段是[1, 2]第三段是[1, 2, 3]以此類推。所以S 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...。題目會(huì)給出T組查詢每組查詢給出兩個(gè)正整數(shù)l和r要求你輸出S[l]到S[r]這個(gè)子序列的和。我們的目標(biāo)就是寫一個(gè)程序能快速處理海量的、端點(diǎn)值巨大的區(qū)間求和查詢。下面我就帶你一步步拆解這個(gè)問題從最直觀的暴力思路開始分析其局限性然后逐步推導(dǎo)出高效的數(shù)學(xué)解法并給出清晰的代碼實(shí)現(xiàn)和關(guān)鍵的避坑指南。2. 暴力模擬法的局限性與復(fù)雜度分析面對(duì)一個(gè)問題最直接的思路往往就是模擬題意。對(duì)于這道題暴力法的思路非常清晰根據(jù)規(guī)律生成數(shù)列S直到長(zhǎng)度覆蓋我們查詢中最大的r。對(duì)于每一次查詢(l, r)遍歷數(shù)組下標(biāo)從l-1到r-1假設(shè)數(shù)組從0開始存儲(chǔ)累加這些位置上的值得到答案。這個(gè)思路的代碼寫起來并不難。但是它的致命缺陷在于空間復(fù)雜度和時(shí)間復(fù)雜度。首先看空間。r的最大值是 10^12。這意味著如果我們想用一個(gè)數(shù)組把整個(gè)數(shù)列存下來需要至少 10^12 個(gè)int類型的存儲(chǔ)單元。一個(gè)int通常占4字節(jié)那么所需內(nèi)存大約是 4 * 10^12 字節(jié) ≈ 4 TB。這顯然遠(yuǎn)遠(yuǎn)超出了任何競(jìng)賽環(huán)境通常內(nèi)存限制在256MB或512MB甚至普通個(gè)人計(jì)算機(jī)的承受能力。所以預(yù)先生成并存儲(chǔ)整個(gè)數(shù)列是不可行的。那我們退一步不存儲(chǔ)只在查詢時(shí)動(dòng)態(tài)生成呢對(duì)于單次查詢(l, r)我們需要生成從第l個(gè)到第r個(gè)數(shù)。在最壞情況下l1, r10^12我們需要生成 10^12 個(gè)數(shù)并進(jìn)行累加。一次這樣的查詢就已經(jīng)無法在規(guī)定時(shí)間通常1秒左右內(nèi)完成了。而題目有最多 10^6 次查詢?nèi)绻看尾樵兌歼@樣暴力生成總計(jì)算量將達(dá)到恐怖的 10^18 次操作這是完全不可接受的。因此暴力法在空間和時(shí)間兩個(gè)維度上都宣告失敗。我們必須尋找數(shù)列的內(nèi)在規(guī)律找到一種方法能夠不依賴具體的數(shù)列值而是通過l和r這兩個(gè)索引直接或間接地計(jì)算出區(qū)間和。注意這是算法競(jìng)賽中常見的思維轉(zhuǎn)折點(diǎn)。當(dāng)數(shù)據(jù)范圍大到無法進(jìn)行樸素操作時(shí)往往意味著題目希望你發(fā)現(xiàn)并利用數(shù)據(jù)的某種數(shù)學(xué)規(guī)律或特殊結(jié)構(gòu)。3. 核心規(guī)律挖掘?qū)⑺饕成涞健岸巍迸c“段內(nèi)位置”要高效計(jì)算我們必須重新審視這個(gè)數(shù)列的結(jié)構(gòu)。數(shù)列S不是雜亂無章的它是由一個(gè)個(gè)等差數(shù)列段首尾相接構(gòu)成的。第1段長(zhǎng)度為1內(nèi)容[1]第2段長(zhǎng)度為2內(nèi)容[1, 2]第3段長(zhǎng)度為3內(nèi)容[1, 2, 3]...第i段長(zhǎng)度為i內(nèi)容[1, 2, 3, ..., i]這是一個(gè)非常規(guī)整的結(jié)構(gòu)。我們的第一個(gè)關(guān)鍵任務(wù)就是給定一個(gè)全局索引pos從1開始快速確定它位于第幾段以及在該段內(nèi)的第幾個(gè)位置。為什么這個(gè)映射如此重要因?yàn)橐坏┪覀冎滥硞€(gè)數(shù)位于第k段的第m個(gè)位置那么這個(gè)數(shù)的值就是m本身。這樣我們就把“求第pos個(gè)數(shù)的值”的問題轉(zhuǎn)化為了“求pos所在的段號(hào)k和段內(nèi)偏移m”的問題。那么如何求k和m呢段號(hào)k的性質(zhì)前k個(gè)段的總長(zhǎng)度構(gòu)成了一個(gè)數(shù)列1, 3, 6, 10, ...。這正是前k個(gè)自然數(shù)的和即total_len 1 2 3 ... k k * (k 1) / 2。映射方法對(duì)于給定的pos我們要找到最小的k使得前k段的總長(zhǎng)度k*(k1)/2 pos。換句話說pos一定位于第k段其中k是滿足k*(k1)/2 pos的最小正整數(shù)。段內(nèi)位置m確定了k我們就知道前k-1段的總長(zhǎng)度為(k-1)*k/2。那么pos在第k段內(nèi)的位置m就是m pos - (k-1)*k/2。并且S[pos]的值就等于m。舉個(gè)例子求pos 8的值。找k我們需要k*(k1)/2 8。k3時(shí)3*4/26 8。k4時(shí)4*5/210 8。所以k4。計(jì)算m前3段總長(zhǎng)3*4/26所以m 8 - 6 2。因此S[8] 2。我們驗(yàn)證一下數(shù)列1, 1,2, 1,2,3, 1,2,3,4,...第8個(gè)數(shù)確實(shí)是2。如何快速計(jì)算這個(gè)k這里就需要用到二分查找。因?yàn)楹瘮?shù)f(k) k*(k1)/2是關(guān)于k的單調(diào)遞增函數(shù)。我們可以在一個(gè)合理的范圍內(nèi)例如[1, 2e6]因?yàn)楫?dāng)k2e6時(shí)總長(zhǎng)度約2e12足以覆蓋pos最大值二分查找滿足f(k) pos的最小k。這樣我們就能在 O(log N) 的時(shí)間內(nèi)完成從pos到(k, m)的映射。4. 高效算法設(shè)計(jì)前綴和思想與分段計(jì)算知道了如何求單個(gè)位置的值我們距離解決區(qū)間和問題還差一步。最笨的辦法是分別求出S[l]和S[r]的值但對(duì)于區(qū)間求和這沒有意義。我們需要的是sum(l, r) S[l] S[l1] ... S[r]。直接遍歷求和是 O(N) 的不可取。這時(shí)前綴和思想就該登場(chǎng)了。如果我們能定義一個(gè)函數(shù)get_sum(x)表示數(shù)列S前x個(gè)元素的和即前綴和那么區(qū)間[l, r]的和就可以表示為sum(l, r) get_sum(r) - get_sum(l-1)所以問題的核心轉(zhuǎn)化為如何高效計(jì)算get_sum(x)我們?cè)俅卫脭?shù)列的分段性質(zhì)。假設(shè)x位于第K段段內(nèi)位置為M即用上一節(jié)的方法求出K和M。那么前x個(gè)數(shù)的和可以分成兩部分計(jì)算完整段的和前K-1個(gè)完整段的所有數(shù)字之和。最后不完整段的部分和第K段的前M個(gè)數(shù)字之和。第一部分完整段的和第i段是一個(gè)等差數(shù)列[1, 2, ..., i]其和為i*(i1)/2。 那么前K-1段的總和就是對(duì)所有i從1到K-1的段內(nèi)和進(jìn)行求和sum_complete Σ_{i1}^{K-1} [i*(i1)/2] (1/2) * Σ_{i1}^{K-1} (i^2 i)根據(jù)平方和公式與等差數(shù)列求和公式Σ_{i1}^{n} i n(n1)/2Σ_{i1}^{n} i^2 n(n1)(2n1)/6令n K-1代入可得sum_complete 1/2 * [ n(n1)(2n1)/6 n(n1)/2 ]化簡(jiǎn)后為了計(jì)算方便通常先通分sum_complete n(n1)(2n1)/12 n(n1)/4 n(n1) * [ (2n1)/12 3/12 ] n(n1) * (2n4) / 12 n(n1)(n2) / 6所以前n個(gè)完整段的總和公式為n(n1)(n2)/6其中n K-1。第二部分不完整段的部分和第K段的前M個(gè)數(shù)是[1, 2, ..., M]這是一個(gè)標(biāo)準(zhǔn)的等差數(shù)列其和為M*(M1)/2。最終get_sum(x)的公式為get_sum(x) (K-1)*K*(K1)/6 M*(M1)/2其中K是x所在的段號(hào)M是x在該段內(nèi)的位置M x - (K-1)*K/2。有了get_sum(x)我們就能在 O(log N) 時(shí)間內(nèi)主要是二分查找K的時(shí)間回答一次區(qū)間和查詢。對(duì)于T次查詢總時(shí)間復(fù)雜度為O(T * log N)在T10^6, N~10^12的情況下完全可行。5. 算法實(shí)現(xiàn)詳解與代碼注釋理論清晰了接下來就是實(shí)現(xiàn)。這里有幾個(gè)細(xì)節(jié)需要特別注意否則很容易出錯(cuò)尤其是在處理大數(shù)運(yùn)算和邊界條件時(shí)。5.1 關(guān)鍵工具函數(shù)二分查找定位段號(hào)我們需要一個(gè)函數(shù)輸入全局索引pos返回它所在的段號(hào)k。由于k*(k1)/2可能超過long long范圍當(dāng)k很大時(shí)我們?cè)诙直容^時(shí)需要小心處理溢出。一個(gè)常見的技巧是使用__int128如果編譯器支持或者進(jìn)行變形比較。這里采用一個(gè)安全且清晰的二分查找方法// 函數(shù)給定位置pos返回所在的段號(hào)k (1-based) long long find_k(long long pos) { long long left 1, right 2e6; // 一個(gè)足夠大的上界因?yàn)閗約等于sqrt(2*pos) while (left right) { long long mid left (right - left) / 2; // 計(jì)算 mid*(mid1)/2注意可能溢出所以用除法判斷 // 判斷 mid*(mid1)/2 pos 是否成立 // 等價(jià)于判斷 mid*(mid1) 2*pos // 為避免mid*(mid1)溢出long long我們移項(xiàng)判斷 mid (2*pos) / (mid1) 是否近似成立這個(gè)方法不精確。 // 更穩(wěn)妥的方法是使用__int128或者用double進(jìn)行近似判斷在安全范圍內(nèi)。 // 由于pos最大1e12mid最大約1.5e6mid*(mid1)最大約2.25e18在long long范圍內(nèi)(9.22e18)。 // 所以對(duì)于本題數(shù)據(jù)范圍直接計(jì)算是安全的。 if (mid * (mid 1) / 2 pos) { right mid; } else { left mid 1; } } return left; }注意這里right的初始值2e6是一個(gè)經(jīng)驗(yàn)值。因?yàn)楫?dāng)pos1e12時(shí)解方程k*(k1)/2 1e12k大約等于 sqrt(2e12) ≈ 1.414e6。設(shè)置2e6作為上界足夠安全且不會(huì)過多增加二分查找的輪數(shù)。5.2 核心計(jì)算函數(shù)求前綴和 get_sum根據(jù)第4節(jié)的推導(dǎo)我們實(shí)現(xiàn)get_sum(x)。需要特別注意當(dāng)x為0時(shí)前綴和應(yīng)為0。// 函數(shù)計(jì)算數(shù)列S前x個(gè)元素的和 long long get_sum(long long x) { if (x 0) return 0; // 1. 找到x所在的段號(hào)K以及段內(nèi)位置M long long K find_k(x); long long prev_total (K - 1) * K / 2; // 前K-1段的總長(zhǎng)度 long long M x - prev_total; // 在第K段中的位置 // 2. 計(jì)算完整段的和前 K-1 段 // sum_complete (K-1) * K * (K1) / 6 // 注意運(yùn)算順序先乘 (K-1)*K再乘(K1)最后除以6可以一定程度上減少中間結(jié)果溢出的風(fēng)險(xiǎn)。 // 但更穩(wěn)妥的方法是使用long long并注意本題數(shù)據(jù)范圍內(nèi)不會(huì)溢出。 long long sum_complete (K - 1) * K / 2 * (K 1) / 3; // 這種寫法利用了 (K-1)*K/2 是整數(shù)先除2再乘(K1)/3但(K1)可能不被3整除。 // 更安全的寫法是 // sum_complete (K - 1) * K * (K 1) / 6LL; // 因?yàn)?(K-1), K, (K1) 三個(gè)連續(xù)整數(shù)中必有一個(gè)是3的倍數(shù)一個(gè)能被2整除所以先除哪個(gè)需要規(guī)劃。 // 我們可以寫成 sum_complete (K - 1) * K / 2; // 這是一個(gè)整數(shù) sum_complete sum_complete * (K 1) / 3; // 現(xiàn)在 sum_complete 是整數(shù) // 3. 計(jì)算不完整段的部分和第K段的前M個(gè)數(shù)之和 long long sum_partial M * (M 1) / 2; // 4. 總和 return sum_complete sum_partial; }避坑點(diǎn)大數(shù)運(yùn)算與整除。在計(jì)算sum_complete (K-1)*K*(K1)/6時(shí)直接相乘再除以6可能會(huì)導(dǎo)致中間結(jié)果溢出long long盡管本題數(shù)據(jù)范圍內(nèi)K最大約1.5e6(K-1)*K*(K1)約 3.375e18小于long long最大值 9.22e18是安全的。但良好的習(xí)慣是注意運(yùn)算順序。我們可以利用(K-1)*K一定能被2整除(K-1)*K*(K1)一定能被6整除的性質(zhì)安排先除2再除3或者先除3再除2。上面的寫法sum_complete (K-1)*K/2; sum_complete sum_complete*(K1)/3;是清晰且安全的。5.3 主邏輯與輸入輸出優(yōu)化算法的主體邏輯非常簡(jiǎn)單對(duì)于每次查詢(l, r)輸出get_sum(r) - get_sum(l-1)。但是在T高達(dá) 10^6 的情況下輸入輸出效率會(huì)成為瓶頸。務(wù)必使用快速的輸入輸出方式。#include iostream #include cstdio // 用于scanf/printf using namespace std; // 這里插入上面定義的 find_k 和 get_sum 函數(shù) int main() { // 關(guān)閉C標(biāo)準(zhǔn)流與C標(biāo)準(zhǔn)流的同步大幅提升cin/cout速度 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin T; // 或者使用 scanf(%d, T); while (T--) { long long l, r; cin l r; // 或者使用 scanf(%lld %lld, l, r); long long ans get_sum(r) - get_sum(l - 1); cout ans \n; // 使用 \n 而不是 endl避免頻繁刷新緩沖區(qū) // 或者使用 printf(%lld\n, ans); } return 0; }輸入輸出優(yōu)化詳解ios::sync_with_stdio(false);這行代碼解除了cin/cout與scanf/printf的同步。默認(rèn)情況下它們是同步的以保證混用時(shí)順序正確但會(huì)帶來額外的開銷。在確定只使用cin/cout時(shí)關(guān)閉同步可以使其速度接近scanf/printf。cin.tie(nullptr);和cout.tie(nullptr);這解除了cin和cout之間的綁定。默認(rèn)情況下每次執(zhí)行cin操作前都會(huì)先刷新cout的緩沖區(qū)以確保在等待輸入前能輸出所有提示信息。在競(jìng)賽中通常不需要這個(gè)特性解除綁定可以進(jìn)一步提升效率。使用\n而不是endlendl會(huì)在輸出換行符的同時(shí)強(qiáng)制刷新輸出緩沖區(qū)而\n只輸出換行符。頻繁刷新緩沖區(qū)會(huì)導(dǎo)致效率低下。在程序結(jié)束時(shí)緩沖區(qū)會(huì)自動(dòng)刷新。對(duì)于極端情況如果使用cin/cout并優(yōu)化后仍感覺不夠快可以換用 C 語言的scanf和printf它們通常更快。6. 邊界條件測(cè)試與常見錯(cuò)誤排查即使算法和代碼都寫出來了也一定要經(jīng)過充分的測(cè)試尤其是邊界條件。以下是幾個(gè)必須測(cè)試的點(diǎn)和常見錯(cuò)誤測(cè)試點(diǎn)1最小邊界輸入T1, l1, r1。預(yù)期輸出1數(shù)列第一個(gè)數(shù)。輸入T1, l1, r2。預(yù)期輸出112。輸入T1, l2, r2。預(yù)期輸出1數(shù)列第二個(gè)數(shù)。測(cè)試點(diǎn)2跨段查詢輸入T1, l3, r6。數(shù)列1(1), 1(2),2(3), 1(4),2(5),3(6)。S[3]2, S[4]1, S[5]2, S[6]3和為 21238。手動(dòng)計(jì)算驗(yàn)證get_sum(6) - get_sum(2)。find_k(6)k3時(shí)3*4/26 6所以K3。prev_total(2*3)/23,M6-33。sum_complete (2*3*4)/64sum_partial3*4/26get_sum(6)10。find_k(2)k2時(shí)2*3/232所以K2。prev_total(1*2)/21,M2-11。sum_complete (1*2*3)/61sum_partial1*2/21get_sum(2)2。結(jié)果10-28正確。測(cè)試點(diǎn)3大數(shù)運(yùn)算與溢出輸入T1, l1, r1000000000000即10^12。這是最大值測(cè)試。確保你的find_k函數(shù)二分上界足夠大且get_sum中的乘法不會(huì)溢出long long。如果使用int會(huì)導(dǎo)致溢出結(jié)果錯(cuò)誤。測(cè)試點(diǎn)4l和r相等且很大輸入T1, l999999999999, r999999999999。測(cè)試單個(gè)大索引值的計(jì)算是否正確。常見錯(cuò)誤排查清單數(shù)據(jù)類型錯(cuò)誤l,r,K,M等變量必須使用long long。int的最大值約2e9遠(yuǎn)小于1e12。二分查找死循環(huán)或錯(cuò)誤檢查while(left right)的循環(huán)條件以及l(fā)eft和right的更新邏輯right mid和left mid 1。確保能找到最小的k滿足條件。公式推導(dǎo)錯(cuò)誤最易錯(cuò)的是完整段求和公式(K-1)*K*(K1)/6。務(wù)必自己推導(dǎo)或驗(yàn)證一遍。可以寫個(gè)小程序暴力計(jì)算前若干項(xiàng)對(duì)比。get_sum(0)處理當(dāng)計(jì)算get_sum(l-1)時(shí)如果l1則參數(shù)為0。你的get_sum函數(shù)必須能正確處理x0的情況返回0。輸入輸出超時(shí)如果沒有進(jìn)行輸入輸出優(yōu)化對(duì)于百萬級(jí)別的查詢很容易超時(shí)。務(wù)必使用scanf/printf或優(yōu)化后的cin/cout。7. 算法擴(kuò)展與思維提升解決這個(gè)問題后我們可以進(jìn)一步思考這種解題思路能應(yīng)用到哪些其他場(chǎng)景1. 分塊與前綴和思想的應(yīng)用本題的本質(zhì)是將一個(gè)具有分塊規(guī)律的序列通過數(shù)學(xué)公式計(jì)算出任意前綴和。這種“分塊公式前綴和”的思想非常強(qiáng)大。例如如果數(shù)列的構(gòu)造規(guī)則發(fā)生變化比如第i段是[i, i1, ..., 2i-1]或者是等比數(shù)列段我們依然可以嘗試找出索引pos到塊號(hào)k和塊內(nèi)偏移m的映射關(guān)系可能需要解二次不等式或使用二分。推導(dǎo)出前k-1個(gè)完整塊的總和公式可能需要用到平方和、立方和或其他數(shù)列求和公式。計(jì)算出第k個(gè)塊的前m個(gè)元素的部分和。最后組合得到前綴和。2. 二分查找的妙用在本例中二分查找用于解決“尋找滿足某種條件的最小整數(shù)”問題即f(k) pos的最小k。這是二分查找的典型應(yīng)用之一查找左邊界。當(dāng)直接求解方程困難時(shí)二分查找提供了一個(gè)O(log N)的解決方案只要判斷函數(shù)f(k)是單調(diào)的。3. 數(shù)學(xué)化簡(jiǎn)的重要性暴力計(jì)算前n個(gè)完整段的和需要O(n)時(shí)間而我們通過數(shù)學(xué)化簡(jiǎn)得到了O(1)的公式n(n1)(n2)/6。這提醒我們?cè)诿鎸?duì)具有數(shù)學(xué)規(guī)律的循環(huán)或累加時(shí)不要急于寫循環(huán)先思考能否用數(shù)學(xué)公式簡(jiǎn)化。這不僅在競(jìng)賽中在實(shí)際工程計(jì)算里也能極大提升效率。4. 應(yīng)對(duì)極端數(shù)據(jù)這道題教會(huì)我們?cè)谠O(shè)計(jì)算法時(shí)必須首先關(guān)注數(shù)據(jù)范圍。10^12和10^6這樣的數(shù)據(jù)范圍直接否決了O(N)或O(N^2)的算法甚至O(sqrt(N))都可能吃力必須向O(log N)或O(1)的方向思考。這訓(xùn)練了我們根據(jù)數(shù)據(jù)范圍反推算法復(fù)雜度的能力?；剡^頭看這道“123”題就像一把鑰匙打開了一類問題的大門。它考察的不僅僅是代碼實(shí)現(xiàn)能力更是問題抽象、數(shù)學(xué)建模和算法優(yōu)化的綜合能力。掌握這道題以后再遇到類似“奇怪?jǐn)?shù)列的區(qū)間和”問題你就能立刻聯(lián)想到“分塊、映射、前綴和公式、二分查找”這套組合拳了。