前缀和与差分

前缀和

什么是前缀和

前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素之和

前缀和有什么用

前缀和是一种预处理,用于降低查询的时间复杂度

例如:给定n个整数,进行m次询问,每次询问给出左端点和右端点,问这两个端点之间所有元素之和是多少.

如果对于每次询问都用for循环一个个相加,那么时间复杂度将高达O(m*n),但是如果用前缀和来处理那么时间复杂度将是O(m)

原理

给定一个数组,命名为a数组

value	10	20	30	40	50	60
index	0	1	2	3	4	5

求出他的前缀和数组,命名为sum数组,为了方便起见我们对sum数组进行一个错位处理

value	0	10	30	60	100	150	210
index	0	1	2	3	4	5	6

如果我想求区间[2,5)之和,即

ans=a2+a3+a4

对于sum数组则有

sum2=a0+a1

sum5=a0+a1+a2+a3+a4

此时我们可以发现:

sum5-sum2=a2+a3+a4=ans

代码

int a[N];
int sum[N+1];
memset(sum, 0, sizeof sum);
for(int i = 0; i < N; i++){
    sum[i + 1] = sum[i] + a[i];
}

差分

什么是差分

差分是逆向的前缀和

差分有什么用

差分是一种预处理,用于降低时间复杂度,对某个区间所有值快速进行加法运算

例如:给定n个整数,进行m次操作,每次操作给出操作的左端点,,右端点和该区间所要加上的值,进行完m次操作之后询问新数组各项的值

如果对于每次询问都用for循环一个个相加,那么时间复杂度将高达O(m*n),但是如果用差分来处理那么时间复杂度将是O(m)

原理

给定一个数组,命名为a数组

value	10	20	30	40	50	60
index	0	1	2	3	4	5

求出他的差分数组,命名为b数组,为了方便起见我们对sum数组进行一个错位处理

value	10	10	10	10	10	10
index	0	1	2	3	4	5

如果我想让区间[2,5)之间所有数加上p,即:

a2+=p,a3+=p,a4+=p

因为有:

a2=b0+b1+b2

a3=b0+b1+b2+b3

a4=b0+b1+b2+b3+b4

此时我们发现他们累加的最后一次相同项都是b2,所以我们只需:

b2+=p

此时演变成了

a2+p == b0+b1+b2+p

a3+p == b0+b1+b2+p+b3

a4+p == b0+b1+b2+p+b3+b4

但是我们会发现计算到a5以及后面所有数时都加上了p:

b0+b1+b2+p+b3+b4+b5 == a5+p

因为我们改变的区间只有[2,5),所以我们要对b5进行操作

b5-=p

此时有:

a5 == b0+b1+b2+p+b3+b4+b5-p

同理后面均不受影响

代码

int a[M];
int b[M + 1];
for(int i = 0; i < M; i++){
    if(!i){
        b[i] = a[i];
        continue;
    }
    b[i] = a[i] - a[i - 1];
}//获得差分

//对区间[l, r)每一项加上p
b[l] += p;
b[r] -= p;

//计算每一项之和
for(int i = 0; i < M; i++){
    if(!i){
        a[i] = b[i];
        continue;
    }
    a[i] = a[i - 1] + b[i];
}