1.前綴和模板
一維前綴和模板
- 1.暴力解法
要求哪段區間，我就直接遍歷那段區間求和。
時間復雜度O(n*q)
- 2.前綴和 ------ 快速求出數組中某一個連續區間的和。
-
-
1）預處理一個前綴和數組
這個前綴和數組設定為dp，dp[i]表示：表示[1,i]區間內所有元素的和。所以，只要題目要求出 【l,r】區間內元素的和，只需要利用前綴和數組dp，計算dp[r] - dp[l-1]即可。
-
所以，使用前綴和算法的時間復雜度是O(n) + O(q)
初始化完成前綴和的時間復雜度是O(n),每次求出區間內所有元素的和的時間復雜度是O(1)，一共要求q次，則復雜度是O(q)。
二維前綴和
二維前綴和模板
1.暴力解法
題目要求求哪個區域的和，就求哪個區域的。
所以就是兩層循環求和即可。
2.前綴和
2.1)填充一個前綴和數組，該前綴和數組表示的含義是：
dp[i][j] ： 從[1,1]位置到->[i,j]位置區域內所有元素的和。
