前綴和算法：高效處理區間求和的利器
目錄
- 引言
- 什么是前綴和
- 前綴和的基本實現
- 前綴和的作用
- 前綴和的典型應用場景
- 前綴和的優缺點分析
- 實戰例題解析
引言
- 區間求和問題的普遍性
- 暴力解法的時間復雜度問題
- 前綴和算法的核心思想
什么是前綴和
- 前綴和的數學定義
通俗來講，前綴和就是從某個位置到最開始的所有數據的和我們可以稱作前綴和
- 一維前綴和的概念
從當前位置到數組開始的所有數據的和。
- 二維前綴和的概念
從當前位置到矩陣和開始((0,0))構成的局部矩陣的所有元素之和。
前綴和的基本實現
前綴和的基本實現非常簡單，通過簡單的遍歷操作就能實現。
前綴和的作用
由于前綴和表示某個位置到數組或矩陣開頭的和，因此前綴和數組可以快速幫助我們獲取任意區間的和。
前綴和的典型應用場景
- 靜態數組的頻繁區間查詢
- 矩陣中的子矩陣求和
- 結合哈希表解決特定問題
- 和為K的子數組個數
- 連續子數組和整除問題
- 數據處理與統計應用
前綴和的優缺點分析
優點
- 查詢時間復雜度O(1)
- 實現簡單高效
- 擴展性強
缺點
- 需要額外O(n)空間
- 原始數組不可變（動態數組需用其他結構）
- 高維時空間消耗大
實戰例題解析
-
一維例題：LeetCode LCR 010. 題目鏈接
解法和思路：
本題通過hash進行記憶化存儲前綴和，存儲我們遍歷時候當前位置之前的所有存在的前綴和，我們可以通過查找hash表判斷是否存在我們需要的前綴和的值。 -
二維例題：LeetCode 304. 二維區域和檢索 - 矩陣不可變
解法和思路:
同一維思想相仿，只不過在構造的時候二維更加復雜：
- 構建prefix(前綴和矩陣) ： prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i -1][j - 1] + matrix[i][j]
- 得到任意一個矩陣的和
Sum({i,j} -> {s,t}) = prefix[s][t] - prefix[s][j - 1] - prefix[i - 1][t] + prefix[i - 1][j - 1]
- 拓展例題：統計美麗子數組數目（結合位運算前綴和）
這道題可以自行思考：leetcode上面也有對應的題解。
示例)
