-
尺取法
-
應用：求一個最小區間
-
原理：通過移動左右兩個指標來確認滿足要求的最小區間
-
基本模板：
while(1) { while( cnt<sum && r<n ){ if( check[r++]==0 ) cnt ++; } if(cnt < sum) break; ans = min(ans,r-l); if( --check[l++]==0 ) cnt --; }
-
-
前綴和
-
應用：對區間和進行O(1)查詢（重復查詢區間和情況）
-
原理：記錄num[i]的前綴和,新陣列的第 i 個數 B[i]是原陣列 A 第 0 到第 i 個數的和
-
模板：
fori { B[i] = i>0 ? B[i-1] + A[i] : A[0]; } -
拓展：多維前綴和：
- sumx,y = sumi-1,j +sumi,j - sumi-1,j-1 + ai,j
-
-
差分
-
應用：O(1)修改區間
-
原理：存盤num[i]-num[i-1]
-
一般與前綴和一起使用：
- 關系：原陣列 = cf[i] + cf[i-1],即差分陣列的前綴和陣列即為原陣列
-
所以可以很方便的通過維護差分陣列來改變原始陣列
-
例：給原始陣列的
l到r區域都加k值//通過差分陣列更新區域 A[l]++;A[r+1]--; //通過前綴和還原 fori : B[i] = B[i-1] + B[i];
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101258.html
標籤：其他
下一篇：求802.11ad協議