代码
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),q = sc.nextInt();
int[] nums = new int[n];
for(int i=0;i<n;i++){
nums[i] = sc.nextInt();
}
//构造初始的差分数组(也是通过更新操作区构造的),把起始的数组当成全0,去给[i,i]区间插入nums[i]的数值。这样构造完毕后,差分数组的前缀和刚好就是初始原数组。
int[] diffArray = new int[n+1]; //因为差分更新的核心操作用有一个是 r+1的操作,因此为了统一边界情况,这里就多申请一个空间。虽然这个diffArray[n]最后是有数的,但是我们不管他就行了。
for(int i=0;i<n;i++){
diffOperator(diffArray,i,i,nums[i]);
}
//根据询问更新差分数组
while(q-->0){
int l = sc.nextInt(),r=sc.nextInt(),c=sc.nextInt();
diffOperator(diffArray,l-1,r-1,c);
}
//根据差分数组恢复原数组。
int res = 0;
for(int i=0;i<n;i++){
res += diffArray[i];
System.out.print(res + " ");
}
}
public static void diffOperator(int[] diffArray,int l,int r,int c){
diffArray[l]+=c;
diffArray[r+1]-=c;
}
}
评析
差分手法的话,其实核心操作就两个:更新差分数组(无需特意构造,因为构造方法跟更新方法是完全一致的。) + 恢复原数组。