静态维护区间加等差数列的求和问题

维护一个数组，先进行m次操作，然后查询每个位置的值，每个操作给定四个参数l,r,a,k表示从l到r依次加上一个首项为a，公差为k的等差数列。
维护d_2数组，表示原数组的二阶差分。

修改操作 

void add(int l,int r,int a,int k)
{
    d2[l]+=a;
    d2[l+1]+=k-a;
    d2[r+1]-=(r-l+1)*k+a;
    d2[r+2]-=(l-r)*k-a;
}

前缀和 

void pre_sum()
{
    for(int i=1;i<=n;++i)
    {
        d2[i]+=d2[i-1];
    }
}

还原操作 

pre_sum();
pre_sum();

模板： 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m,d2[MAXN],l,r,a,k;
void add(int l,int r,int a,int k)
{
    d2[l]+=a;
    d2[l+1]+=k-a;
    d2[r+1]-=(r-l+1)*k+a;
    d2[r+2]-=(l-r)*k-a;
}
void pre_sum()
{
    for(int i=1;i<=n;++i)
    {
        d2[i]+=d2[i-1];
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d %d",&l,&r,&a,&k);
        add(l,r,a,k);
    }
    pre_sum();
    pre_sum();
    for(int i=1;i<=n;++i)
    {
        printf("%d%c",d2[i],i==n?'\n':' ');
    }
    return 0;
}

算法原理

见https://blog.nowcoder.net/n/b0401b709aa540f0af78dfc8e66813fb

如果需要动态维护区间加等差数列的求和问题，可使用线段树或者参