差分数组是一种高效处理区间更新的数据结构

差分数组是一种高效处理区间更新的数据结构技巧，核心思想是存储相邻元素的差值而非元素本身，将区间操作转化为端点操作，从而将区间更新的时间复杂度从 O(n) 降到 O(1)。

#include<bits/stdc++.h>
using namespace std;
int a[1000000],D[1000000];
int main()
{
    int n,p,l,r,x,small=108;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        D[i]=a[i]-a[i-1];
    }
    while(p--){
        cin>>l>>r>>x;
        D[l]+=x,D[r+1]-=x;
    }
    for(int i=1;i<=n;i++){
        a[i]=D[i]+a[i-1];
        if(a[i]<small) small=a[i];
    }
    cout<<small;
    return 0;
}