题目描述

一维差分

样例

import java.util.Scanner;

public class Main {
   /* 
    原数组长度为n,差分数组长度为n+1

    差分数组适当比原数组开大点空间，差分数组和原数组的第一个元素相同，所以循环的i都成1开始，位置0的值为0.

    private static final int N = 100010;
    private static final int[] a = new int[N + 5];//原数组
    private static final int[] b = new int[N + 5];//差分数组


    一个数组给区间[l, r]中的每个数操作c，可以转化为对一个数组的差分数组区间[l, r]操作c：
    B[l] += c, B[r + 1] -= c     左端点加c     右端点+1的位置减c 

    private static void difference(int left, int right, int c) {
        b[left] += c;
        b[right + 1] -= c;
    }
    可以直接用这个方法，根据原数组去求出差分数组，注意是求差分数组。

    或者for (int i = n + 1; i > 0; i -- ) b[i] -= b[i - 1]; 去求差分数组  i要从n+1开始

    差分数组各元素的和一定为0，说明正数总合=负数总合

    */
    private static final int N = 100010;
    private static final int[] a = new int[N + 5];
    private static final int[] b = new int[N + 5];

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }

        //求差分数组
        for (int i = 1; i <= n; i++) {
            difference(i,i,a[i]);
        }

        while (m-- > 0) {
            int left = in.nextInt();
            int right = in.nextInt();
            int c = in.nextInt();
            difference(left, right, c);
        }

        //差分数组还原成原数组 前一个加后一个
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            System.out.print(b[i] + " ");
        }
    }

    private static void difference(int left, int right, int c) {
        b[left] += c;//左端点加c
        b[right + 1] -= c;//右端点+1的位置减c 
    }
}

————————————————————————————————————————————————————————————

证明差分数组各元素的和一定为0，说明正数总合=负数总合