前缀和和差分算法-一维差分

一维差分概念

对于一个数列 a[i]，我们需要维护的数据是“相邻两个数之差”。这种策略是，令p[i]=a[i]-a[i-1]即相邻两数的差。我们称数列 p[i] 为数列 a[i]的差分数列。差分数列可以快速的在某个区间加上加上或者减去一个数。

一维差分数组的构建

差分可以看成前缀和的逆运算
首先给定一个原数组a：a[1], a[2], a[3], a[n];
然后我们构造一个数组b ： b[1], b[2], b[3], b[i];
使得 a[i] = b[1] + b[2] + b[3] + , + b[i]；
1.a[1]=b[1];
2.a[2]=b[1]+b[2];
3.a[3]=b[1]+b[2]+b[3];
由1，2，3得
b[1]=a[1];
b[2]=a[2]-b[1]=a[2]-a[1];
b[3]=a[3]-b[1]-b[2]=a[3]-a[2];
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
一维差分的构建用p[i]=a[i]-a[i-1]即可。
一维差分题目模板

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[] arr=new int[n+10];
        for(int i=1;i<=n;i++)
        {
            arr[i]=in.nextInt();
        }
        long[] pre=new long[n+10];
        for(int i=1;i<=n;i++)
        {
            pre[i]=arr[i]-arr[i-1];//建立差分数组
        }
        while((m--)>0)
        {
            int l=in.nextInt();
            int r=in.nextInt();
            int k=in.nextInt();
            pre[l]+=k;//使用差分数组
            pre[r+1]-=k;
        }
        for(int i=1;i<=n;i++)
        {
            pre[i]+=pre[i-1];//差分数组求前缀和还原为原数组
            System.out.print(pre[i]+" ");
        }
    }
}

使用差分数组
pre[l]+=k;
pre[r+1]-=k;