Java 代码
首先差分是 s[i] = h[1] + h[2] + … + h[i]
细化: h[1] = s[1]
h[2] = s[2] - s[1]
h[3] = s[3] - s[2]
那么h[i] = s[i] - s[i - 1];
即h[i]的前缀和就是a[i]
对一段区间加固定值,可以转换为在差分中首加一个值,尾减一个值,因为在h[l]加一个值后
s[l] = 原s[l] + c, s[l + 1] = 原s[l + 1] + 1…, 即所有s[l]之后的值都会+c,但是咱们要求的是区间
所以要在尾减一个值来抵消 即 s[r + 1] = 原s[r + 1] - c 与之前的+ c抵消,最后就只剩下区间的了
import java.util.*;
public class Main{
static int N = 100010;
static int[] h = new int[N]; // 差分函数.
static int[] s = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 1; i <= n; i ++){
s[i] = scan.nextInt();
h[i] = s[i] - s[i - 1];
}
while(m -- > 0){
int l, r, c;
l = scan.nextInt();
r = scan.nextInt();
c = scan.nextInt();
getDiv(l, r, c);
}
for(int i = 1; i <= n; i ++){
s[i] = s[i - 1] + h[i];
System.out.print(s[i] + " ");
}
}
static void getDiv(int l, int r, int c){
h[l] += c;
h[r + 1] -= c;
}
}