差分

先说一道题目：
给出一个数组，m个操作每次操作从l到r位置的每个数加上z
最后给出q个查询，查询每次l到r位置的区间和

差分做法：

设d[i] = a[i]-a[i-1] (1<i≤n,d[1]=a[1])；
设f[i] = f[i-1]+d[i] (1<i≤n,f[1]=d[1]=a[1])；
设sum[i] = sum[i-1]+f[i] (1<i≤n,sum[1]=f[1]=d[1]=a[1])。

举个例子 求一下1-3的区间和
图片说明

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxx = 100010;
int n,m,q,l,r,z;
int a[maxx],d[maxx],f[maxx],sum[maxx];
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=m;i++){
        cin>>l>>r>>z;
        d[l]+=z;
        d[r+1]-=z;
    }
    for(int i=1;i<=n;i++){
        f[i] = f[i-1]+d[i];
        sum[i]=sum[i-1]+f[i];
    }
    for(int i=1;i<=q;i++){
        cin>>l>>r;
        cout<<sum[r]-sim[l-1]<<endl;
    }
    return 0;
}