带权前缀和

很多题目里，要求的已经不再是简单的区间和，而是这种形式：

\(a_l\cdot1 + a_{l+1}\cdot2 + a_{l+2}\cdot3 + \cdots + a_r\cdot(r-l+1)\)注意，这里每一项前面的系数都不一样。

这说明题目已经不再只是“求一段区间的和”，而是在求：

区间中的元素，按照它们在区间中的位置重新编号后的加权和。

如果每次都直接暴力计算，时间复杂度会很高。

这时就需要提前预处理，把这些带权信息先存起来，之后快速查询。

带权前缀和的定义

\(w_i = \sum_{k=1}^{i} k \cdot a_k\)

含义是：

- 第 1 个元素乘 1 - 第 2 个元素乘 2 - 第 3 个元素乘 3 - …… - 第 i 个元素乘 i

再把它们累加起来。

普通前缀和记录的是“前面总共有多少”。

带权前缀和记录的是“前面这些数按位置乘起来之后总共有多少”。

\(w_i = w_{i-1} + i \cdot a_i\)

本质上仍然是在做前缀累加，只不过累加对象换成了 \(i\cdot a_i\)

典型问题

如果要求区间 [l,r] 的带权和：

\(a_l\cdot1 + a_{l+1}\cdot2 + a_{l+2}\cdot3 + \cdots + a_r\cdot(r-l+1)\)

那么答案是：

\((w_r - w_{l-1}) - (l-1)(s_r - s_{l-1})\)

带权前缀和 \(w_i\) 里，元素 \(a_k\) 乘的是原下标 \(k\)。

但题目要求的区间带权和里，元素 \(a_k\) 乘的是区间内编号 \(k-l+1\)。

这两个系数相差多少呢？

\(k - (k-l+1) = l-1\)

对于区间内的每一个元素，它在原下标权重里都“多乘了 \(l-1\) 倍"

所以你先用 \(w_r - w_{l-1}\) 把整段的“原下标加权和”取出来，

再减去这一段中每个元素都多出来的 \(l-1\) 倍，也就是：

\((l-1)(s_r-s_{l-1})\)

这样就正好变成区间内重新编号后的带权和。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
long long a[N], s[N], w[N];

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        w[i] = w[i - 1] + 1LL * i * a[i];
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        long long ans = (w[r] - w[l - 1]) - 1LL * (l - 1) * (s[r] - s[l - 1]);
        cout << ans << '\n';
    }

    return 0;
}