差分数组

对于一个数组D,要求其前i项和,SUM = \sum\limits_{i=1}^{n} {D_i}
令f[i] = D[i] – D[i-1]      i \in [2, n], 当i=1时f[1] = D[1] – 0 = D[1]
简单性质:
D[i]的值是f[i]的前缀和,即D[i] =  \sum\limits_{j=1}^{i} {f_i}
计算D[i]的前缀和, SUM = \sum\limits_{i=1}^{n} {D_i} = \sum\limits_{i = 1} ^{n} \sum\limits_{j = 1}^{i}{f_j} = ( n – i + 1 ) * {f_i}
这种结构可以快速处理一段区域数据的频繁的加减操作,只需要f[L] += item, f[R+1] -= item就可以了.其中f[R + 1] = f[R+1] – f[R] f[R + 1] – item = f[R+1] – (f[R] + item),对区间的两个端点进行操作,就不必对一段区域进行操作了.
相关例题:
HDU1556
差分数组的模板题.
arr[i] = arr[i-1] + f[i]; 是对f[i] = arr[i] – arr[i-1]的一个变形

#include  <bits/stdc++.h>

using namespace std;
int t, a, b;
vector<int> arr, f;
int main()
{
    while ( scanf("%d", &t) && t )
    {
        arr.clear();f.clear();
        arr.resize(t + 1);
        f.resize(t + 1);
        //f[1] = arr[1];
        int tmp = t;
        while ( tmp -- )
        {
            scanf("%d %d", &a, &b);
            f[a] ++; f[b+1] --;
        }
        for ( int i = 1; i <= t; i ++  ) 
        {
            arr[i] = arr[i-1] + f[i];
            printf("%d",arr[i]);
            if ( i != t ) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

luogu_P1083

二分查找+差分数组.用二分查找来寻找m中不能使条件满足的第一个请求.
f[i]表示arr[i]的差分数组,对租借天数的left和right进行操作:

f[arr[i].left] += arr[i].weight;
f[arr[i].right+1] -= arr[i].weight;

根据性质1, 如果f[i]的前缀和超过了那一天的教师数量a[i]就说明这一次的请求是需要修改的.

#include  <bits/stdc++.h>

using namespace std;

struct node
{
    int left, right, weight;
}  arr[1000010];

long long int f[1000010], n, m, a[1000010];

bool check( int day )
{
    long long int sum = 0;
    memset(f, 0, sizeof(f));
    for ( int i = 1; i <= day; i ++ )
    {   
        f[arr[i].left] += arr[i].weight;
        f[arr[i].right+1] -= arr[i].weight;
    }
    for ( int i = 1; i <= n; i ++ )
    {
        sum += f[i];
        if ( sum > a[i] ) return 0;
    }
    return 1;
}

int main()
{

    scanf("%lld %lld", &n, &m);
    for ( int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    for ( int i = 1; i <= m; i ++ ) scanf("%d %d %d", &arr[i].weight, &arr[i].left, &arr[i].right);
    if ( check(m) ) { printf("0\n"); return 0; }
    int left = 1, right = m;
    while ( right > left )
    {
        int mid = ( left + right ) / 2;
        if ( check(mid) ) left = mid + 1 ;
        else right = mid;
    }
    //cout << left << ' '<<right <<endl;
    printf("-1\n%d\n",right);

    return 0;
}

codeforce1355C

x_i \in [A, B]
y_i \in [B, C]
z_i \in [C, D]
只要满足x_i + y_i > z_i, 观察可得,需要求满足[x_i + B, x_i + C]>[C, D]的那些组合的个数.
设置一个差分数组a[i], a[i]记录长度为i的边(或者边的和)的个数.
设置一个maxn, 为题目所给的ABCD相加不会超过的一个值
先遍历一遍区间x \in [A, B]求出[x_i + B, x_i + C]也就是

for ( int i = a; i <= b; i ++ )
    {
        arr[b + i] ++;
        arr[c + i + 1] --;
    }

再根据性质1就能够求出两边和为i的数量了

for ( int i = 1; i <= maxn; i ++  ) arr[i] += arr[i-1];

再进行一次累加,求出前缀和.

for ( int i = c; i <= d; i ++ ) sum += ( arr[maxn] - arr[i] );

arr[maxn] – arr[i]表示比z_i大的两边和的总数.

#include <bits/stdc++.h>

using namespace std;

int a, b, c, d;
const int maxn = 1000080;
long long int arr[maxn+1];

int main()
{
    scanf("%d %d %d %d", &a, &b, &c, &d);
    memset(arr, 0, sizeof(arr));
    for ( int i = a; i <= b; i ++ )
    {
        arr[b + i] ++;
        arr[c + i + 1] --;
    }
    for ( int i = 1; i <= maxn; i ++  ) arr[i] += arr[i-1];
    //求两边和为i的项目的个数
    for ( int i = 1; i <= maxn; i ++  ) arr[i] += arr[i-1];
    //前缀和
    long long int sum = 0;
    for ( int i = c; i <= d; i ++ ) sum += ( arr[maxn] - arr[i] );
    printf("%lld\n",sum);
    return 0;
}