前缀和例题:子矩阵的和AcWing796-Java版-Toy模板网

这篇具有很好参考价值的文章主要介绍了前缀和例题:子矩阵的和AcWing796-Java版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前缀和例题:子矩阵的和AcWing796-Java版,算法,矩阵,java,算法,蓝桥杯,数据结构

//前缀和模板提,在读入数据的时候就可以先算好前缀和的大小
//计算前缀的时候用:g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]);
//计算结果的时候用:g[x2][y2] - g[x1 - 1][y2]- g[x2][y1-1] + g[x1 -1][y1 - 1] + "\n"
//一些重复加的地方都需要减掉,如计算前缀和的时候g[i-1][j-1]包括在了前面的g[i][j-1] + g[i-1][j],多减去一次
//g[x1 - 1][y1 - 1]也被包括在前面两项表达式,只需减去一次

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
	static int n,m,q;
	static int N = 1010;
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static int[][] g = new int[N][N];
	
	public static void main(String[] args) throws IOException{
		String[] init = in.readLine().split(" ");
		n = Integer.parseInt(init[0]);
		m = Integer.parseInt(init[1]);
		q = Integer.parseInt(init[2]);
		
		for(int i = 1;i <= n;i ++) {
			init = in.readLine().split(" ");
			for(int j = 1;j <= m;j ++) {
				g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]);
			}
		}
		
		while(q-- > 0) {
			init = in.readLine().split(" ");
			int x1 = Integer.parseInt(init[0]);
			int y1 = Integer.parseInt(init[1]);
			int x2 = Integer.parseInt(init[2]);
			int y2 = Integer.parseInt(init[3]);
			out.write(g[x2][y2] - g[x1 - 1][y2]- g[x2][y1 - 1] + g[x1 -1][y1 - 1] + "\n");
		}
		in.close();
		out.flush();
	}
	
}

前缀和例题:一维版前缀和

进阶版:二维前缀和-2 文章来源地址https://www.toymoban.com/news/detail-784133.html

到了这里，关于前缀和例题:子矩阵的和AcWing796-Java版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！