前缀和与差分

一维前缀和

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int q=sc.nextInt();
        int []a=new int[n+1];
        int []sum=new int[n+1];
        for(int i=1;i<=n;i++){
          a[i]=sc.nextInt();
          sum[i]=sum[i-1]+a[i];
        }
        for(int i=0;i<q;i++){
        int l=sc.nextInt();
        int r=sc.nextInt();
        System.out.println(sum[r]-sum[l-1]);
        }
        sc.close();
    }
}

二维前缀和

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 q=scan.nextInt();
        int [][]a=new int[n+1][m+1];
        int [][]sum=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            a[i][j]=scan.nextInt();
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
          }
        }
        for(int i=0;i<q;i++){
          int x1=scan.nextInt();
          int y1=scan.nextInt();
          int x2=scan.nextInt();
          int y2=scan.nextInt();
          int res=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
          System.out.println(res);
        }
        scan.close();
    }
}

一维差分

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 q=scan.nextInt();
        int []a=new int[n+10];
        int []b=new int[n+10];
        int []c=new int[n+10];
        for(int i=1;i<=n;i++){
          a[i]=scan.nextInt();
          b[i]=a[i]-a[i-1];
        }
        for(int i=1;i<=q;i++){
          int l=scan.nextInt();
          int r=scan.nextInt();
          int d=scan.nextInt();
          b[l]+=d;
          b[r+1]-=d;
        }
        for(int i=1;i<=n;i++){
          c[i]=c[i-1]+b[i];
        }
        for(int i=1;i<=n;i++)
          System.out.print(c[i]+" ");
        scan.close();
    }
}

二维差分

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 q=scan.nextInt();
        int [][]a=new int[n+10][m+10];
        int [][]b=new int[n+10][m+10];
        int [][]c=new int[n+10][m+10];

        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
              a[i][j]=scan.nextInt();
              b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
          }
        }
        for(int i=1;i<=q;i++){
          int x1=scan.nextInt();
          int y1=scan.nextInt();
          int x2=scan.nextInt();
          int y2=scan.nextInt();
          int d=scan.nextInt();
          b[x1][y1]+=d;
          b[x2+1][y1]-=d;
          b[x1][y2+1]-=d;
          b[x2+1][y2+1]+=d;
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            b[i][j]=b[i][j]+b[i][j-1]+b[i-1][j]-b[i-1][j-1];
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            System.out.print(b[i][j]+" ");
          }
          System.out.println();
        }
        scan.close();
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇