题意

给定数组 $a_1,a_2,\dots,a_n$，求所有连续区间的元素和之和：

$$\sum_{1 \le l \le r \le n} \sum_{i=l}^{r} a_i$$

暴力思路

最直接枚举每个区间 $[l,r]$，再求区间和，如果每次重新求和是 $O(n^3)$；用前缀和可以优化到 $O(n^2)$。
但当 $n$ 很大时，$O(n^2)$ 仍然会超时。

正解
换一个角度，不枚举区间，而是考虑每个 $a_i$ 会被多少个区间包含。

一个区间 $[l,r]$ 包含 $a_i$，需要满足：

$$l \le i \le r$$

左端点 $l$ 可以选：

$$1,2,\dots,i$$

一共有 $i$ 种。

右端点 $r$ 可以选：

$$i,i+1,\dots,n$$

一共有 $n-i+1$ 种。

所以包含 $a_i$ 的区间数量是：

$$i(n-i+1)$$

因此 $a_i$ 对答案的总贡献是：

$$a_i \cdot i \cdot (n-i+1)$$

上面这种做法我们可以称为拆贡献

拆贡献是什么

拆贡献是一种把“整体求和”改写成“单个对象贡献之和”的思维方式。

直接枚举所有方案通常很慢。拆贡献的想法是：

不要枚举每个方案怎么算答案；
改成枚举每个基本对象，看它在多少个方案中产生贡献。

也就是把：

$$\sum_{\text{方案 } S} f(S)$$

改写成：

$$\sum_{\text{基本对象 } x} \text{贡献值}(x) \times \text{出现次数}(x)$$

它的数学本质是 交换求和顺序。