织梦零基础做网站,永久链接生成器,2021年国内国际时事,网站优化要怎么做//前缀和模板提,在读入数据的时候就可以先算好前缀和的大小 //计算前缀的时候用: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][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
