摘要
“全区间函数值求和”是一个常见的算法模式：给定数组 \(a[1..n]\)，我们要对所有子数组 \([L, R] (1 ≤ L ≤ R ≤ n)\) 计算某个函数 \(f(L, R)\) 的值，并把它们相加，求：
\(\sum_{1 \leq L \leq R \leq n} f(L, R)\)
这类问题在比赛和面试中非常常见。它的关键不在于穷举所有 \(O(n^2)\) 区间（这在 \(n ≤ 2e5\) 时不可行），而是找出 数学化、可组合或可分解 的技巧，把复杂的区间求和变成对元素（或位、或状态）的贡献统计。
核心思路：拆贡献 / 线性化
别一上来就想着硬算所有区间，先问自己：能不能把 \(f(L, R)\) 拆成一些小块，然后每块分别统计它的“贡献”次数？
想象一下，你在数乐高积木的总重量。直接把所有积木搭好再称？太累了。不如一个个积木称好，看看每个积木在多少个模型里出现过，再加起来。
常见两种拆法：
- 线性可分型：比如子数组和。
- 计数归约型（比如某个性质是否出现）：例如 “某一位在区间 \(OR\) 中为 \(1\)” 或者 “区间 \(XOR\) 在某一位为 \(1\)” ，可以按位来算次数。
模板：
- 找到“原子”——最小的计算单元（元素 / 位 / 状态）。
- 对每个原子，数它在多少个区间里发挥作用（最大值、最小值、某位为 \(1…\)）。
- 把所有原子的贡献累加，就是最终答案。
常见的好搭档有：单调栈（找最大最小值）、双指针（滑动窗口统计）、哈希表（计数）、位运算（按位分治）等。
例 1：所有子数组的和
问题描述：
给定一个长度为 \(n\) 的数组 \(a[1..n]\)，你的任务是计算所有子数组的和的总和。
解题思路：
这个问题中 \(f(L, R) = a_L + a_{L + 1} + …… + a_R \)。
固定某个元素 \(a_i\)，它会出现在多少个子数组中？左端点 \(L\) 有 \(i\) 种取法，右端点 \(R\) 有 \(n – i + 1\) 种取法，总出现次数：
\(c_i = i × (n – i + 1)\)
于是总和：
\(S = \sum_{i=1}^{n} a_i \cdot i \cdot (n – i + 1)\)
仅需一次遍历，复杂度 \(O(n)\)。
解决代码：
ll ans = 0;
for (int i = 1; i <= n; ++i)
ans += a[i] * i * (n - i + 1);\(1 – based\) 版， \(ans\) 就为答案。
例 2：所有子数组的 XOR 和
题目链接：P3917 异或序列 – 洛谷
问题描述：
给定一个长度为 \(n\) 的数组 \(a[1..n]\)，对每个子数组进行异或计算，求所有子数组异或值求总和。
解题思路：
这个问题中 \(f(L, R) = a_L \oplus a_{L + 1} \oplus …… \oplus a_R \)。
按位拆分，利用前缀异或的性质来统计。
先计算前缀异或数组：
\(pre[0] = 0, \quad pre[i] = pre[i-1] \oplus a[i]\)
对于某一位 \(b\)，子区间异或结果在这一位为 \(1\) 的条件是：
\(pre[R] \oplus pre[L-1] \quad \text{在第 } b \text{ 位为 } 1\)
这等价于：
\(pre[R] \text{ 和 } pre[L-1] \text{ 在第 } b \text{ 位不同，一个是 } 0 \text{，一个是 } 1\)
因此，统计所有前缀异或中该位为 \(1\) 的个数 \(cnt1\)，和该位为 \(0\) 的个数 \(cnt0\)。
每一个“\(1\)”都可以和每一个“\(0\)”组成一个有效区间，使得该位的子区间异或为 \(1\)，因此贡献区间数为：
\(count_b = cnt0 \times cnt1\)
该位的总贡献为：
\(count_b \times 2^b\)
最终总和是所有位贡献的累加，复杂度为 \(O(n \cdot B)\)，其中 \(B\) 是二进制位数。
解决代码：
vector<int> pre(n + 10, 0);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] ^ a[i];
ll ans = 0;
for (int i = 0; i < 31; ++i)
{
ll cnt0 = 0, cnt1 = 0;
for (int j = 0; j <= n; ++j)
{
if (pre[j] & (1 << i))
++cnt1;
else
++cnt0;
}
ans += cnt0 * cnt1 * (1 << i);
}\(1 – based\) 版， \(ans\) 就为答案。
例 3：所有子串中任一字符最大出现次数之和
原题链接：https://codeforces.com/contest/2121/problem/G
问题描述：
给定长度为 \(n\) 的二进制字符串 \(s = s_1 s_2 \cdots s_n\)，定义函数 \(f(p)\) 为字符串 \(p\) 中某个字符出现的最大次数。例如：
- \(f(00110) = 3\)（字符 ‘\(0\)‘ 出现 \(3\) 次）
- \(f(01) = 1\)
求所有子串 \(s_l s_{l+1} \cdots s_r\)（满足 \(1 \leq l \leq r \leq n\)）的 \(f\) 值之和。
解题思路：
题目要求我们计算所有区间的 \(f(s[l \dots r])\) 的值。
根据题目描述，函数定义为：
\(f(s[l \dots r]) = \max(cnt_0, cnt_1)\)
其中，\(cnt_1\) 是区间内字符 ‘\(1\)‘ 的个数，\(cnt_0\) 是区间内字符 ‘\(0\)‘ 的个数。
通过：
\(\max(a, b) = \frac{a + b + |a – b|}{2}\)
可得：
\(\max(cnt_0, cnt_1) = \frac{cnt_0 + cnt_1 + |cnt_0 – cnt_1|}{2}\)
其中 \(cnt_0 + cnt_1\) 就是区间内全部元素个数既区间长度，由于区间长度为 \(len = r – l + 1\)
可以将 \(f\) 转换为：
\(f = \frac{len + |cnt_1 – cnt_0|}{2}\)
通过以上分析，问题就转化为两个子问题：
- 求所有子数组长度的和，即 \(P(L, R)\)；
- 求所有子数组中两个元素差值绝对值的和，即 \(F(L, R)\)。
这两个都是经典的全区间函数值求和问题。
求 P(L, R)
所有长度为 \(i\) 的子数组数量是 \(n – i + 1\)。
所以所有子数组长度之和为：
\(P(L, R) = \sum_{i=1}^n i \times (n – i + 1)\)
这部分直接通过简单的数学求和即可。
求 F(L, R)
先将字符串中字符 ‘\(1\)’ 赋值为 \(+1\)，字符 ‘\(0\)’ 赋值为 \(-1\)，
构造前缀和数组 \(pre：\)
\(pre[i] = pre[i-1] + (s[i] == ‘1’ ? 1 : -1)\)
那么任意区间的差值为：
\(cnt_1 – cnt_0 = pre[r] – pre[l-1]\)
问题转化为求数组 \(pre\) 中所有两两元素差的绝对值之和。
求数组中两两元素绝对值的差值也是一个非常经典的问题。计算方法：将 \(pre\) 数组排序，记排序后的数组仍为 \(pre\)。根据数学性质，对于排序数组，第 \(i\) 个元素对答案的贡献是：
\(pre[i] \times (2i – n)\)
最终，将 \(P(L, R)\) 和 \(F(L, R)\) 相加除以 \(2\) 即得到所有区间的 \(f\) 的总和。
解决代码：
vector<ll> pre(n + 10, 0);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + (s[i] == '1' ? 1 : -1);
ll ans = 0;
for (ll i = 1; i <= n; ++i)
ans += i * (n - i + 1ll);
sort(pre.begin(), pre.begin() + n + 1);
for (ll i = 0; i <= n; ++i)
ans += pre[i] * (i - (n - i));
ans /= 2;\(1 – based\) 版， \(ans\) 就为答案。
相关题目推荐：
1.P12177 [蓝桥杯 2025 省 Python B] 异或和 – 洛谷
3.https://codeforces.com/contest/2131/problem/F
5.https://atcoder.jp/contests/abc423/tasks/abc423_e
