解决的是在数组的某个区间加上一个常数的问题，复杂度从O(n)->O(1)

1、原来有一个数组a，
2、定义一个差分数组b
3、把a中的数在b中插一遍
4、然后再进行各个区间[l, r]的插入

其中有一个很很关键的数组下标问题：

• 从0 or 1开始
• b数组要多开一个空间 (n + 1)

两种其实都可行，只不过从0开始的做法，在求前缀和时不用处理b[0],直接才b[1]开始

// 下标从0开始
for(int i = 0; i < n; i++) insert(b, i, i, a[i]);

for(int i = 1; i <n; i++) {
    b[i] = b[i - 1] + b[i];
    System.out.print(b[i] + " ");
}

System.out.print(b[0] + " ");
for(int i = 1; i < n; i++) {
    b[i] = b[i - 1] + b[i];
    System.out.print(b[i] + " ");
}

public static void insert(int[] a, int l, int r, int c){
    a[l] += c;
    a[r + 1] -= c;
}

// 下标从1开始
for(int i = 1; i <= n; i++) insert(b, i, i, a[i]);

for(int i = 1; i <n; i++) {
    b[i] = b[i - 1] + b[i];
    System.out.print(b[i] + " ");
}

for(int i = 1; i <= n; i++) {
    b[i] = b[i - 1] + b[i];
    System.out.print(b[i] + " ");
}

public static void insert(int[] a, int l, int r, int c){
    a[l] += c;
    a[r + 1] -= c;
}