java的前缀和算法_java前缀和算法

前缀和的概念

对于一个给定的数组A，它的前缀和数组S中S[i]表示从第1个元素到第i个元素的总和，用公式表示为：

Si=A1+A2+A3+...+An

前缀和的作用

在O(1)的时间求出数组任意区间的区间和。

降低求解的复杂度

算法模板

int n=10;
int [] arr=new int [n];
long [] sum=new long[n+1];
for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+arr[i-1];
}

例题解析

给定一个长度为n的数组a以及m个查询

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

请对每个查询输出一个答案，答案对10^9+7取模

输入格式

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

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

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

输出格式

输出m行，每行一个整数，表示查询的答案对10^9+7取模的结果。

package Accommodate;
 
import java.util.*;
 
public class Main1 {
 
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int q=scan.nextInt();
		int arr[]=new int [n];
		for(int i = 0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		long mod=(long)1e9+7;
		long [][]sum=new long[6][n+1];
		for(int i=1;i<6;i++) {
			for(int j=1;j<=n;j++) {
				sum[i][j]=sum[i][j-1]+(long)Math.pow(arr[j-1],i);
				sum[i][j]%=mod;
			}
		}
		 
		for(int i=0;i<q;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);
		}
	
}
}