差分數組：了解

差分數組：

差分數組的思路其實是通過差分，遞推出經過部分區間修改後的原數組，例如我們要對區間進行加減操作，最終求某個區間的值

舉個栗子：

a[ ]	1	2	3	4	5
差分p[ ]	1	1	1	1	1

修改區間：

| [1 5] +2 | [2,3] -1| [1 3] +3 |      

修改後的差分p[ ]	6	1	-1	1
修改後的a[ ]	6	6	7	6	7

講解：

我們隻需要讓差分數組​

​p[l]+=w p[r+1]-=w​

​​ 我們可以通過最初的差分​

​p[1]​

​​得到修改後的​

​a[]​

​​,隻需要通過遞推式即可得到，由于​

​p[1]​

​​的差分是其本身我們就可以利用遞推式得到修改後的原數組。遞推式：​

​p[i]+=p[i-1]​

​

​​例題推薦：區間​​

題解：

#include<bits/stdc++.h>
using namespace std;
//差分數組
//區間和
#define ll long long
const  int maxn=1000001;
ll a[maxn],p[maxn];
int main()
{
    ll n,q;
    //cout<<maxn;
    scanf("%lld %lld",&n,&q);
    for(ll i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        p[i]=a[i]-a[i-1];
    }
    while(q--)
    {
        ll l,r,op,w;
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld %lld %lld",&l,&r,&w);
            p[l]-=w;
            p[r+1]+=w;
        }
        else
        {
            scanf("%lld %lld %lld",&l,&r,&w);
            p[l]+=w;
            p[r+1]-=w;
        }
    }
    for(ll i=1;i<=n;i++)
    {
        p[i]=p[i]+p[i-1];
        a[i]=a[i-1]+p[i];
    }
    ll l,r;
    scanf("%lld %lld",&l,&r);
    printf("%lld\n",a[r]-a[l-1]);

}