差分数组

差分数组使用场景：

• 频繁对数组的一段区间进行增加或者减去同一个值，快速对区间做加减法
• 询问区间和问题

差分数组定义：

存在数组A[n]，定义差分数组d[n]满足:

性质：

从l到r对原数组都加上k：

for(int i=l,i<=r;i++){
      A[n]+=k;
}

但对于差分数组的变化是：

d[l]+=k;
d[r+1]-=k;

此时我们仍然可以通过差分数组，通过前缀和来恢复数组A。
由上述可以发现差分数组可以快速对区间做加减法，由此这个可以配合前缀和数组以及树状数组来完成一些操作;
以前缀和数组来举例，原数组中的元素i+K，那么前缀和数组从i开始往后都要+i,通过构建前缀和数组的差分数组，只需要改动一个元素即可。

例题：

美团校招题：路由器
https://www.nowcoder.com/questionTerminal/220361995bb64de08dc47c646ee111ab

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int cnt = 0;
        int[] router = new int[n]; //差分数组
        for(int i = 0; i < n; i++){
            int signal = scanner.nextInt(); //当前路由器的信号
            int start = Math.max(i - signal, 0);//router[0]=router[0]-router[-1],router[-1]=0没有具体表示出来;
            router[start]++;
            if(signal + i + 1 < n){
                router[signal + i + 1]--;
            }
        }
        //通过前缀和 恢复原数组
        int sum = 0;
        for(int i = 0; i < router.length; i++){
            sum += router[i];
            if(sum >= k){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}