前缀和——储物点的距离

题目：

一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。 每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？ 比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j ) dist就是储物点间的距离。

题解：

using namespace std;

const long long mod = 1000000007;
const int N = 200010;
long long a[N], b[N], c[N];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++){
        scanf("%lld", &a[i]);
        a[i] = (a[i] + a[i - 1]) % mod;
    }
    for (int i = 1; i <= n; i++){
        scanf("%lld", &b[i]);
    }
    for (int i = 1; i <= n; i++){
        c[i] = (b[i] * a[i] + c[i - 1]) % mod;//求出把当前点的东西拿到1需要的花费
        b[i] = (b[i] + b[i - 1]) % mod;
    }
    for (int i = 0; i < m; i++){
        long long ans;
        long long x, l, r;
        scanf("%lld%lld%lld", &x, &l, &r);
        if (x <= l){//三种情况见p1
            ans = (c[r] - c[l - 1]) - a[x] * (b[r] - b[l - 1]);
        }
        else if (x >= r){
            ans = a[x] * (b[r] - b[l - 1]) - (c[r] - c[l - 1]);
        }
        else{
            ans = (c[r] - c[x - 1]) - a[x] * (b[r] - b[x - 1]) + a[x] * (b[x] - b[l - 1]) - (c[x] - c[l - 1]);
        }
        ans = (ans % mod + mod) % mod;
        printf("%lld\n", ans);
    }
    
    
    return 0;
}

自己刚开始想用暴力，但是会超时，采用变相的前缀和可以很好的避免这个问题。

p1