跳至主要内容

10. 巧用資料結構

第 10 章 巧用資料結構

📄️ 10.10 前綴和與積分圖

一維的前綴和(cumulative sum, cumsum),二維的積分圖(summed-area table, image integral)是通過將每個位置之前的一維線段或二維矩形的數值預先計算並儲存,從而加速後續的查詢與計算。如果需要對前綴和或積分圖的值進行查找,可以將其存入雜湊表;如果需要對每個位置記錄前綴和或積分圖的值,則可以將其儲存到一維或二維數組中,通常還伴隨著動態規劃。