俄语购物网站建设斗蟋蟀网站建设

俄语购物网站建设,斗蟋蟀网站建设,个人注册商标步骤,青海公路工程建设总公司网站一. 核心思想#xff1a;提前算好#xff0c;一劳永逸1.想象一下#xff0c;你有一本很厚的书#xff0c;每次有人问你#xff1a;“从第 3 页到第 97 页#xff0c;一共有多少字#xff1f;”最笨的方法#xff1a;翻到第 3 页#xff0c;一页一页地数#xff0c;一…一. 核心思想提前算好一劳永逸1.想象一下你有一本很厚的书每次有人问你“从第 3 页到第 97 页一共有多少字”最笨的方法翻到第 3 页一页一页地数一直数到第 97 页。如果这个人反复问你不同区间比如 5~10 页20~80 页等等你每次都要重新数会非常累。2..前缀和的聪明做法在别人问你之前你先做一张表第 1 页累计字数 前 1 页总字数第 2 页累计字数 前 2 页总字数第 3 页累计字数 前 3 页总字数……第 n 页累计字数 前 n 页总字数这张表就叫“前缀和数组”记作prefix[i]表示前 i 页的总字数。二. 如何回答区间和问题如果问“第 L 页到第 R 页的总字数”怎么办用前缀和思想前 R 页的总字数 prefix[R]前 L-1 页的总字数 prefix[L-1]那么第 L 页到第 R 页的总字数 prefix[R] - prefix[L-1]一次减法就得到结果不用一页页重新加。三. 举例理解假设原数组每页字数pages [2, 5, 3, 1, 6] 假设只有5页前缀和数组我们通常让 prefix[0] 0方便计算prefix[0] 0 prefix[1] pages[0] 2 prefix[2] pages[0] pages[1] 2 5 7 prefix[3] 7 3 10 prefix[4] 10 1 11 prefix[5] 11 6 17即prefix [0, 2, 7, 10, 11, 17]问第 2 页到第 4 页的总字数对应 pages[1] ~ pages[3]注意编程索引原数组对应是 5 3 1 9用前缀和L2, R4这里用 1-based 页数举例对应数组索引 L1~3 可能需要调整但思路一致常见是 L,R 是原数组的索引从0开始我们统一理解概念如果用 1-based 页号第 2 页到第 4 页对应原数组下标 1 到 34个元素 pages[1],pages[2],pages[3]。用 0-based 索引解释编程常用原数组 arr [2, 5, 3, 1, 6] 长度 n5前缀和 prefix 长度 n1prefix[k] 表示 arr[0] 到 arr[k-1] 的和。问 arr[1] arr[2] arr[3] 531 9计算prefix[4] arr[0]arr[1]arr[2]arr[3] 2531 11prefix[1] arr[0] 2arr[1]~arr[3] 的和 prefix[4] - prefix[1] 11 - 2 9 ✅通用公式索引从0开始sum(arr[L] ... arr[R]) prefix[R1] - prefix[L]为什么是 R1因为 prefix[i] 表示前 i 个元素的和即 arr[0]~arr[i-1]所以到 arr[R] 为止一共是 R1 个元素和是 prefix[R1]。再减去前 L 个元素的和 prefix[L]即 arr[0]~arr[L-1]就得到 arr[L]~arr[R] 的和。四. 为什么在蓝桥杯等竞赛中常用因为很多题会多次询问“某个区间的和”如果每次用循环去加时间复杂度是 O(区间长度)问 m 次最坏是 O(m*n)可能超时。用前缀和预处理前缀和数组O(n)每次查询O(1)m 次查询O(n m)效率大大提升。五. 二维前缀和如果是一个矩阵二维数组问某个子矩阵的和也可以用类似思想但公式稍微复杂一点本质是先算好prefix[i][j]表示从 (0,0) 到 (i-1,j-1) 的矩形内所有数的和。那么任意子矩形 (x1,y1) 到 (x2,y2) 的和可以用几个前缀和加减一次得到容斥原理。六. 总结一下核心前缀和数组的第 i 项存储的是原数组前 i 项的和通常 i 从0开始prefix[0]0以便统一公式。目的是用 O(1) 时间计算任意区间和用右端前缀和 减 左端前缀和。关键记住公式0-based 原数组索引 L,Rsum[L..R] prefix[R1] - prefix[L]七.例题区间和查询1.题目描述​给定一个长度为 n 的整数数组 arr有 m 次查询。每次查询给定两个整数 L 和 R0 ≤ L ≤ R n求 arr[L] 到 arr[R] 的区间和。输入格式​第一行整数 n第二行n 个整数表示数组 arr第三行整数 m接下来 m 行每行两个整数 L, R输出格式​输出 m 行每行一个整数表示对应查询的区间和样例输入5 1 3 5 7 9 3 0 4 1 3 2 2样例输出25 15 52.解题思路1. 暴力解法不可取对于每次查询都遍历 arr[L] 到 arr[R] 并求和每次查询时间复杂度O(R-L1)最坏 O(n)m 次查询总时间复杂度O(m×n)当 n, m 较大时比如 10⁵ 级别会超时2. 前缀和解法最优步骤预处理前缀和数组创建长度为 n1 的数组 prefixprefix[0] 0prefix[i] prefix[i-1] arr[i-1] (1 ≤ i ≤ n)prefix[i] 表示 arr[0] 到 arr[i-1] 的和计算区间和公式要计算 arr[L] 到 arr[R] 的和前 R1 个数的和 prefix[R1]前 L 个数的和 prefix[L]区间和 prefix[R1] - prefix[L]时间复杂度分析预处理O(n)每次查询O(1)总复杂度O(n m)3.代码实现import java.util.Scanner; public class PrefixSumExample { public static void main(String[] args) { Scanner sc new Scanner(System.in); // 1. 读取数组长度 int n sc.nextInt(); // 2. 读取原数组 int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } // 3. 构建前缀和数组 // prefix[i] 表示 arr[0] 到 arr[i-1] 的和 long[] prefix new long[n 1]; // 使用long防止溢出 prefix[0] 0; // 初始值前0个元素和为0 for (int i 1; i n; i) { // prefix[i] 前i-1个元素的和 第i-1个元素(arr[i-1]) prefix[i] prefix[i - 1] arr[i - 1]; } // 4. 读取查询次数 int m sc.nextInt(); // 5. 处理每次查询 for (int q 0; q m; q) { int L sc.nextInt(); int R sc.nextInt(); // 核心公式arr[L]到arr[R]的和 prefix[R1] - prefix[L] long sum prefix[R 1] - prefix[L]; System.out.println(sum); } sc.close(); } }4.详细演示用样例数据1.输入5 1 3 5 7 9 3 0 4 1 3 2 22.处理过程构建原数组arr [1, 3, 5, 7, 9]构建前缀和数组prefix[0] 0 prefix[1] prefix[0] arr[0] 0 1 1 prefix[2] prefix[1] arr[1] 1 3 4 prefix[3] prefix[2] arr[2] 4 5 9 prefix[4] prefix[3] arr[3] 9 7 16 prefix[5] prefix[4] arr[4] 16 9 25prefix [0, 1, 4, 9, 16, 25]处理查询查询1L0, R4sum prefix[5] - prefix[0] 25 - 0 25 ✓查询2L1, R3sum prefix[4] - prefix[1] 16 - 1 15 ✓查询3L2, R2sum prefix[3] - prefix[2] 9 - 4 5 ✓八.关键点总结为什么要用 long 类型防止大数相加时溢出int 范围约 ±21亿为什么 prefix 长度是 n1为了统一处理 L0 的情况prefix[0]0 让计算更简洁公式的理解技巧prefix[i] 前 i 个元素的和要 arr[L]~arr[R]一共有 (R-L1) 个元素包含 arr[R] 的最小区间是 [0, R]有 R1 个元素不包含 arr[L] 的最小区间是 [0, L-1]有 L 个元素所以sum prefix[R1] - prefix[L]九.模板1.一维前缀和1. 基础模板public class PrefixSumTemplate { // 模板1标准一维前缀和 public static long[] getPrefixSum(int[] arr) { int n arr.length; long[] prefix new long[n 1]; // 长度n1 prefix[0] 0; // 初始化 for (int i 1; i n; i) { prefix[i] prefix[i - 1] arr[i - 1]; } return prefix; } // 查询区间和 [L, R]闭区间0-based索引 public static long queryRangeSum(long[] prefix, int L, int R) { // 公式sum(L,R) prefix[R1] - prefix[L] return prefix[R 1] - prefix[L]; } // 完整使用示例 public static void example1() { int[] arr {1, 3, 5, 7, 9}; long[] prefix getPrefixSum(arr); // 查询 [1, 3] 的和 long sum queryRangeSum(prefix, 1, 3); System.out.println(Sum of [1,3]: sum); // 输出 15 } }2. 原地构建模板节省空间public class PrefixSumInPlace { // 模板2原地修改原数组为前缀和 public static int[] buildPrefixSumInPlace(int[] arr) { for (int i 1; i arr.length; i) { arr[i] arr[i - 1]; } return arr; } // 查询需要处理边界 public static int queryInPlace(int[] prefix, int L, int R) { if (L 0) { return prefix[R]; } return prefix[R] - prefix[L - 1]; } }2.二维前缀和1. 标准模板public class PrefixSum2DTemplate { // 构建二维前缀和 // matrix: m行n列的矩阵 public static long[][] getPrefixSum2D(int[][] matrix) { int m matrix.length; int n matrix[0].length; long[][] prefix new long[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { // 核心递推公式 prefix[i][j] prefix[i-1][j] prefix[i][j-1] - prefix[i-1][j-1] matrix[i-1][j-1]; } } return prefix; } // 查询子矩阵和 // (x1,y1) 左上角(x2,y2) 右下角0-based索引 public static long querySubMatrix(long[][] prefix, int x1, int y1, int x2, int y2) { // 转为1-based索引 x1; y1; x2; y2; // 容斥原理公式 return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] prefix[x1-1][y1-1]; } // 使用示例 public static void example2D() { int[][] matrix { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; long[][] prefix getPrefixSum2D(matrix); // 查询左上角(1,1)到右下角(2,2)的和 long sum querySubMatrix(prefix, 1, 1, 2, 2); System.out.println(Submatrix sum: sum); // 输出 28 } }3.常用变形模板1. 带取模的前缀和public class PrefixSumWithMod { // 处理大数取模的场景 public static int[] getPrefixSumMod(int[] arr, int mod) { int n arr.length; int[] prefix new int[n 1]; prefix[0] 0; for (int i 1; i n; i) { prefix[i] (prefix[i-1] arr[i-1]) % mod; } return prefix; } // 查询带取模的区间和 public static int queryRangeMod(int[] prefix, int L, int R, int mod) { int sum (prefix[R1] - prefix[L]) % mod; return sum 0 ? sum mod : sum; // 处理负数 } }2. 差分数组模板前缀和的逆运算public class DifferenceArray { // 差分数组用于区间增减操作 public static int[] getDifferenceArray(int[] arr) { int n arr.length; int[] diff new int[n]; diff[0] arr[0]; // 第一个元素特殊处理 for (int i 1; i n; i) { diff[i] arr[i] - arr[i-1]; } return diff; } // 对区间[L,R]的所有元素增加val public static void addToRange(int[] diff, int L, int R, int val) { diff[L] val; if (R 1 diff.length) { diff[R1] - val; } } // 从差分数组恢复原数组就是求前缀和 public static int[] recoverArray(int[] diff) { int n diff.length; int[] arr new int[n]; arr[0] diff[0]; for (int i 1; i n; i) { arr[i] arr[i-1] diff[i]; } return arr; } }4.记忆口诀1. 一维前缀和预处理prefix[i] prefix[i-1] arr[i-1] 查区间sum(L,R) prefix[R1] - prefix[L]长度prefix长度是n1起点prefix[0] 0公式右端1 减 左端2. 二维前缀和构建prefix[i][j] 上 左 - 左上 当前 查询sum 右下 - 右上 - 左下 左上5.实战练习模板import java.util.Scanner; public class PrefixSumPractice { public static void main(String[] args) { Scanner sc new Scanner(System.in); // 读取数据 int n sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } // 构建前缀和 long[] prefix new long[n 1]; for (int i 1; i n; i) { prefix[i] prefix[i - 1] arr[i - 1]; } // 处理查询 int q sc.nextInt(); while (q-- 0) { int l sc.nextInt(); int r sc.nextInt(); // 注意题目索引是0-based还是1-based // 如果是1-based输入要转换为0-based // 0-based: sum prefix[r1] - prefix[l] // 1-based: sum prefix[r] - prefix[l-1] long sum prefix[r 1] - prefix[l]; System.out.println(sum); } sc.close(); } }6.注意事项索引转换竞赛题有时用1-based输入需要转换为0-based数据范围可能溢出用long空间优化如果不需要保留原数组可以原地修改初始化prefix[0] 0很重要边界检查确保索引不越界