本质上有动态规划的思想。文章目录一、一维前缀和二、二维前缀和三、零边界一、一维前缀和牛客 DP34.【模板】前缀和设dp[i]表示数组前i个元素之和并额外定义dp[0] 0dp[i] dp[i - 1] arr[i]查询闭区间[l, r]时dp[r]包含第1个到第r个元素再减去第1个到第l - 1个元素sum(l, r) dp[r] - dp[l - 1]代码中的数组名虽然是dp但它保存的是预处理得到的前缀和不是动态规划中的最优子结构结果。importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intqin.nextInt();int[]arrnewint[n1];long[]dpnewlong[n1];for(inti1;in1;i){arr[i]in.nextInt();dp[i]dp[i-1]arr[i];}while(in.hasNextInt()){intain.nextInt();intbin.nextInt();System.out.println(dp[b]-dp[a-1]);}}}题目中的元素绝对值可达10^9区间和可能超过int范围因此前缀和数组使用long[]。二、二维前缀和牛客 DP35.【模板】二维前缀和设dp[i][j]表示左上角(1, 1)到右下角(i, j)这一整块矩形的元素和。构造时先相加上方矩形与左侧矩形但它们重复计算了左上角重叠区域因此需要减去一次再加上当前元素dp[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1] arr[i][j]查询左上角(x1, y1)到右下角(x2, y2)的子矩形时同样使用容斥sum dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] dp[x1 - 1][y1 - 1]前两次减法去掉目标矩形上方与左侧的区域但左上角区域被减了两次所以最后要补回一次。importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intmin.nextInt();intqin.nextInt();int[][]arrnewint[n1][m1];long[][]dpnewlong[n1][m1];for(inti1;in1;i){for(intj1;jm1;j){arr[i][j]in.nextInt();dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]arr[i][j];}}while(in.hasNextInt()){intx1in.nextInt();inty1in.nextInt();intx2in.nextInt();inty2in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]);}}}三、零边界为什么要把原数组向后平移一位如果一维前缀和直接把dp[0]作为第一个值不是更符合直觉吗但是这样我们在实操的时候会遇到许多不便之处往往需要繁杂的分类讨论因此我们补出值为0的边界用来统一公式。例如查询从第1个元素开始第1个元素结束的区间时公式会访问dp[1 - 1]也就是dp[0]。二维前缀和同理当查询区域贴着上边界或左边界时公式会访问第0行或第0列。预留零边界后不需要为这些情况额外分类也不会出现负数下标从而我们花费了少量的空间换来了简洁的代码优雅的思路和性能的提升。