蓝桥杯试题：区间次方和（前缀和）

活动发起人@小虚竹想对你说：

这是一个以写作博客为目的的创作活动，旨在鼓励大学生博主们挖掘自己的创作潜能，展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴，那么，快来参加吧！我们一起发掘写作的魅力，书写出属于我们的故事。我们诚挚邀请你参加为期14天的创作挑战赛！

提醒：在发布作品前，请将不需要的内容删除。

一、问题描述

给定一个长度为 nn 的整数数组 aa 以及 mm 个查询。

每个查询包含三个整数 l,r,kl,r,k 表示询问 l∼rl∼r 之间所有元素的 kk 次方和。

请对每个查询输出一个答案，答案对 109+7109+7 取模。

输入格式

第一行输入两个整数 n,mn,m 其含义如上所述。

第二行输入 nn 个整数 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。

接下来 mm 行，每行输入三个整数 l,r,kl,r,k 表示一个查询。

输出格式

输出 mm 行，每行一个整数，表示查询的答案对 109+7109+7 取模的结果。

样例输入

样例输出

14
99
12

二、前缀和算法

1. 前缀和的定义

给定一个数组 nums，其前缀和数组 prefix 的第 i 项表示原数组前 i 个元素的和（从第 0 个到第 i-1 个元素）。

· 特点：前缀和数组的长度比原数组多 1，且首项 prefix[0] = 0。

2. 核心作用

· 快速计算区间和：若需计算原数组 nums[a..b] 的和（闭区间），只需 prefix[b+1] - prefix[a]。

· 时间复杂度优化：预处理阶段为 O(n)，单次查询区间和的时间降为 O(1)。

3. Java代码示例

java">public class PrefixSumExample {public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5};int[] prefix = computePrefixSum(nums);// 输出前缀和数组：[0, 1, 3, 6, 10, 15]System.out.println(java.util.Arrays.toString(prefix));// 计算区间和 [1..3] (原数组元素 2+3+4=9)int sum = getRangeSum(prefix, 1, 3);System.out.println("Sum of nums[1..3]: " + sum); // 输出 9}/*** 计算前缀和数组* @param nums 原始数组* @return 前缀和数组，长度为 nums.length + 1*/public static int[] computePrefixSum(int[] nums) {int n = nums.length;int[] prefix = new int[n + 1];for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}return prefix;}/*** 通过前缀和数组快速计算区间和 [a, b]* @param prefix 前缀和数组* @param a 区间起始索引（原数组）* @param b 区间结束索引（原数组）* @return 区间和*/public static int getRangeSum(int[] prefix, int a, int b) {return prefix[b + 1] - prefix[a];}
}

4. 应用场景

1. 多次区间和查询：如统计数组中多个子数组的总和。

2. 滑动窗口问题：配合双指针技术快速计算窗口内元素的和。

3. 动态规划：作为状态转移的基础，例如最长连续子数组和问题。

二、试题代码展示

java">import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n = scan.nextInt();int m = scan.nextInt();int[] a = new int[n];for(int i = 0 ; i < n ;i++){a[i]  = scan.nextInt();}long mod = (long)1e9 + 7;long[][] sum = new  long[6][n + 1];  //sum[i][j]代表前j个元素的i次方和//计算前缀和，k从1--5（假设 + 避免超时 + 符合实际）for(int i = 1 ; i < 6 ; i++){for(int j = 1 ; j <= n ; j++){sum[i][j] = sum[i][j - 1] + (long)Math.pow(a[j-1] , i);}}for(int i = 0; i < m ; i++){int l = scan.nextInt() - 1;int r = scan.nextInt() - 1;int k = scan.nextInt();long ans = sum[k][r + 1] + mod -sum[k][l]; //加末端取模 保证结果为正ans %= mod;System.out.println(ans);}scan.close();}
}