当前位置：首页 > article >正文

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

article 2025/2/25 0:27:18

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

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

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. 动态规划：作为状态转移的基础，例如最长连续子数组和问题。

二、试题代码展示

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();
    }
}

查看全文

http://www.kler.cn/a/559614.html