先把累加和算好,之後查任何區間和都 O(1)。用空間換查詢速度。
O(1) 搞定,不用每次把區間重加一遍。建表花 O(n)、之後每次查詢 O(1) —— 查詢越多次越划算。
prefix[i] = arr 前 i 個的總和 —— 習慣讓 prefix[0]=0、prefix[i]=prefix[i-1]+arr[i-1]。
區間和公式 —— arr[l..r] 的和 = prefix[r+1] − prefix[l](大段減掉前面多算的那段)。
建一次、查無數次 —— 前處理 O(n),之後每次查詢 O(1)。
用空間換時間 —— 多存一個 n+1 大小的前綴陣列。
大量「區間和」查詢 —— 問很多次「l 到 r 的和」,前綴和完勝每次重加的 O(n)。
和為 k 的子陣列 —— 前綴和配雜湊表,把 O(n²) 壓到 O(n)(範例 3)。
差分陣列(反操作) —— 要「很多段區間各加值」,只動兩端、最後用前綴和還原(範例 8)。
二維版 —— 算任意子矩陣的和也能 O(1)(範例 6)。
n+1 的前綴陣列。記下「從起點到每根電線桿」的距離,任兩根之間的距離 = 相減就好。
每筆交易後的餘額都記著,某段期間的收支 = 期末餘額 − 期初餘額。
開票記「到第 N 箱為止的累計票」,某幾箱的票數 = 相減。
先由左往右建前綴和 prefix[i]=prefix[i-1]+arr[i-1](琥珀是相加的來源、紫色是新算出的)。建好後問「index 2 ~ 4 的區間和」,只要 prefix[5] − prefix[2](綠色兩格相減),O(1)!按「下一步」。
從建表 + 區間查詢、和為 k 的子陣列、樞紐索引、除自己以外的乘積,到二維前綴和、差分陣列、前綴 XOR。
❌ 前綴索引差一格 —— prefix[0]=0 的慣例下,arr[l..r] = prefix[r+1] − prefix[l];經典 off-by-one 雷。
❌ 只查一兩次還建表 —— 建表本身 O(n),查太少次不划算,直接加就好。
❌ 忘了 seen={0:1} 初始 —— 「和為 k」那類要先放一個空前綴,否則會漏掉「從頭開始」的子陣列。
❌ 一邊查一邊改陣列 —— 前綴和是「靜態」快照;資料會變動要用樹狀陣列 / 線段樹。
[3,1,4,1,5,9,2] 的前綴和陣列是什麼?index 2~4 的區間和怎麼用相減算出來?O(1)?公式是什麼?O(n),而不是 O(n²)?把答案打到對話裡,我幫你對。