对于一个数组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] = D[R+1] – D[R] f[R + 1] – item = D[R+1] – (D[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;
}
二分查找+差分数组.用二分查找来寻找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;
}
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;
}