---
title: "贡献法"
description: "不枚举每个区间，改成统计每个元素被算了几次。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 贡献法

![](https://img.dailyup.xyz/optimized/8208353655603-8e82e158-f564-443d-b7f8-8a8a6f45a9fb.jpg)

有一类题目的字面要求是「所有子区间的某种量加起来是多少」。按字面去做，枚举所有区间是 $O(n^2)$，$n$ 到 $10^5$ 就超时了。贡献法换个角度数数，往往能把复杂度降一个量级。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| CSP-J/S 第一轮 | 换个角度统计的思想常出现在阅读程序与完善程序中 | 全章 |
| GESP C++ 八级 | 考点 8：算法优化，理解不同方法在时空复杂度上的差异 | 全章 |
| CSP-J/S 入门级 | 2.4 基本运算：位运算（按位拆开统计） | 例二、例四、例五、练习 2/5/6/7 |
| CSP-J/S 提高级 | 4.4 算法策略：单调栈配合贡献法（子数组最值之和） | 例三、练习 3 |

## 核心思路

正向统计是：对每个区间，把区间里所有元素的贡献加起来。

贡献法是：对每个元素，统计它在多少个区间里被算到，乘上它自己的值。

$$\text{答案} = \sum_{\text{每个元素}} (\text{元素的值} \times \text{它被统计到的次数})$$

关键问题从「有多少个区间」变成了「这个元素出现在哪些区间里」。后者往往能用左边界和右边界的组合数快速算出来。

## 例一：所有子数组的元素和之和

给定数组，求所有连续子数组的和再全部加起来的和。

朴素做法要枚举左右端点，$O(n^2)$。换成贡献法看元素 $a[i]$（下标从 1 开始）：

- 一个子数组包含 $a[i]$，当且仅当左端点在 $1$ 到 $i$ 之间，右端点在 $i$ 到 $n$ 之间。
- 左端点有 $i$ 种选法，右端点有 $n - i + 1$ 种。
- 所以 $a[i]$ 被 $i \times (n - i + 1)$ 个子数组包含。

$$\text{答案} = \sum_{i=1}^{n} a[i] \times i \times (n - i + 1)$$

```cpp
long long ans = 0;
for (int i = 1; i <= n; i++) {
    ans += 1LL * a[i] * i * (n - i + 1);
}
cout << ans << endl;

一次循环就够了，$O(n)$。注意这里乘出来可能超过 `int`，所以要用 `1LL` 把运算提升到 `long long`。

## 例二：按位统计

求所有子数组按位或的和，或者按位与的和。这类题不能整体统计，但可以**按二进制位分别算**。

以按位或为例。对第 $b$ 位，我们想知道有多少个子数组的或值在这一位上是 1。正面算不好算，就算反面：这一位全是 0 的子数组有多少个。

把数组中第 $b$ 位为 0 的位置连成一段段连续区间，每一段长度为 $len$ 的全零段能贡献 $len \times (len + 1) / 2$ 个全零子数组。总数减去全零的，就是这一位为 1 的子数组个数，乘上 $2^b$ 累加到答案里。

```cpp
long long ans = 0;
for (int b = 0; b < 31; b++) {
    long long zero = 0;      // 这一位全为 0 的子数组数
    long long len = 0;       // 当前连续的全零段长度
    for (int i = 1; i <= n; i++) {
        if ((a[i] >> b) & 1) {
            zero += len * (len + 1) / 2; // 结算这一段
            len = 0;
        } else {
            len++;
        }
    }
    zero += len * (len + 1) / 2;
    long long total = 1LL * n * (n + 1) / 2; // 子数组总数
    ans += (total - zero) * (1LL << b);
}
cout << ans << endl;

按位处理是位运算题的通用套路：整体难算的，拆成 31 位，每一位单独统计再合并。

> 上面假设所有数都是非负整数且小于 $2^{31}$（`int` 的范围）。如果题目里出现了负数或者更大的数，位数的上界要相应调整。

## 例三：每个数作为最大值的区间数

求所有子数组的最大值之和。对每个 $a[i]$，算出「以 $a[i]$ 为最大值的子数组」有多少个，再乘上 $a[i]$。

设左边第一个严格大于 $a[i]$ 的位置是 $L$，右边第一个大于等于 $a[i]$ 的位置是 $R$（一边严格、一边非严格，是为了避免相同的数被重复统计）。那么左端点可以在 $L+1$ 到 $i$ 之间，右端点在 $i$ 到 $R-1$ 之间：

$$\text{个数} = (i - L) \times (R - i)$$

$L$ 和 $R$ 可以用**单调栈**在 $O(n)$ 内全部求出。这正是《栈与队列》里单调栈的经典用法。

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

const int N = 100005;
long long a[N];
int L[N], R[N];

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];

  // L[i]：左边第一个「严格大于」a[i] 的位置，没有则记 0
  stack<int> st;
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    L[i] = st.empty() ? 0 : st.top();
    st.push(i);
  }

  // R[i]：右边第一个「大于等于」a[i] 的位置，没有则记 n+1
  while (!st.empty()) st.pop();
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    R[i] = st.empty() ? n + 1 : st.top();
    st.push(i);
  }

  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += a[i] * 1LL * (i - L[i]) * (R[i] - i); // 以 a[i] 为最大值的子数组个数
  }
  cout << ans << endl;
  return 0;
}

注意两边的判断条件不一样：左边的栈弹出条件是 `<=`，右边是 `<`。一边严格、一边非严格，相同的数才不会在两个位置上各被统计一次。

## 例四：所有数对的按位与之和

求所有数对 $(i, j)$（$i < j$）的按位与之和。

这题和「异或和」是同一套框架，**区别只在「什么样的数对能让这一位变成 1」**：

| 运算 | 第 $b$ 位结果为 1 的条件 | 贡献 |
| --- | --- | --- |
| 异或 | 两个数这一位**不同** | $c_1 \times c_0$ |
| 与 | 两个数这一位**都是 1** | $c_1 \times (c_1 - 1) / 2$ |
| 或（数对） | 两个数这一位**至少一个为 1** | $\dfrac{n(n-1)}{2} - \dfrac{c_0(c_0-1)}{2}$ |

其中 $c_1$ 是这一位为 1 的数的个数，$c_0 = n - c_1$。

```cpp
long long ans = 0;
for (int b = 0; b < 20; b++) {
    long long c1 = 0;
    for (int i = 0; i < n; i++) c1 += (a[i] >> b) & 1;
    ans += c1 * (c1 - 1) / 2 * (1LL << b); // 从 c1 个里任取两个
}

**这张表值得背下来**：三种位运算的数对/子数组统计，都是「按位拆 + 数清这一位为 1 的个数 + 算出方案数」。

## 例五：子数组的按位与之和

求所有**连续子数组**按位与之和。注意这已经不是数对问题了，而是子数组问题。

按位看第 $b$ 位：一个子数组的与在这一位为 1，当且仅当**这个子数组里所有数在这一位都是 1**。

所以做法和例二（按位或）正好相反：

- 例二（或）：把**为 0** 的位置切成段，数「全零子数组」的个数，再用总数减去；
- 例五（与）：把**为 1** 的位置切成段，数「全一子数组」的个数，直接累加。

```cpp
long long ans = 0;
for (int b = 0; b < 20; b++) {
    long long one = 0, len = 0;
    for (int i = 1; i <= n; i++) {
        if ((a[i] >> b) & 1) {
            len++;              // 这一位是 1，段长加一
        } else {
            one += len * (len + 1) / 2; // 段结束，结算这一段的全一子数组
            len = 0;
        }
    }
    one += len * (len + 1) / 2;
    ans += one * (1LL << b);   // 全一子数组的个数 × 这一位的权重
}

一个长度为 $len$ 的「全 1 段」里，任意选左右端点都得到一个全一子数组，共 $len(len+1)/2$ 个。

> 把例二和例五对着读一遍，能看出一个很好用的思维定式：**「或」统计 1 的补集（全 0 段），「与」统计 1 本身（全 1 段）**。因为「或为 1」只要有一个 1，不好直接数；而「与为 1」要求全是 1，正好是连续的 1。

## 什么时候想到贡献法

- 题目要求「所有子区间的某种量之和」，按区间枚举是 $O(n^2)$ 及以上。
- 每个元素的「影响」可以用它左右两侧的位置范围描述。
- 涉及位运算，可以按位拆开统计（数对型和子数组型的公式不同）。
- 要求「所有子数组的最大值/最小值之和」，用单调栈求出每个元素作为最值的边界。

## 复杂度对比

| 做法 | 复杂度 |
| --- | --- |
| 枚举左右端点 | $O(n^2)$，位运算题还要再乘位数 |
| 贡献法 | $O(n)$，或 $O(n \log n)$（需要排序、单调栈） |

## 常见易错点

- 相乘时忘记开 `long long`。$n = 10^5$ 时 $i \times (n-i+1)$ 最大约 $2.5 \times 10^9$，已经超过 `int`。
- 统计「包含某元素的区间数」时，左右端点的可行范围容易数错一位，画个图示最稳。
- 处理相同的数时，单调栈一定要做到「一边严格、一边非严格」，否则重复计数。
- 贡献法是「换角度」，不是「省略计算」。答案算错的常见原因是贡献次数推错，而不是代码写错。
- **混用「数对」与「子数组」的公式**。数对是 $\binom{c_1}{2}$，子数组是 $\sum\frac{len(len+1)}{2}$，两者不能互相套用。
- **分段统计漏掉最后一段**。循环结束后 `len` 里可能还存着一段没结算的连续区间，必须再补一次。
- **`c1*(c1-1)/2` 或 `len*(len+1)/2` 用 `int`**。$10^5$ 量级相乘就到 $10^{10}$，必须提升到 `long long`（写成 `1LL * ...` 或先把变量声明成 `long long`）。

## 练习

下面的练习都已经收录进题库，点击每道题的「在线评测练习」可以直接提交评测；题面与数据范围以题库为准，课堂上的分析和代码则只围绕本章的「贡献法」展开，方便对照前面的核心思路直接套用。

### 练习 1：所有子数组的和之和

在线评测练习：[P1517 所有子数组的和之和](https://dailyup.run/tasks/601)

#### 题目描述

给定 $n$ 个整数，求它所有连续子数组的元素和之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有连续子数组元素和的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $|a_i| \le 10^4$。

#### 输入输出样例

输入

```
3
1 2 3

输出

```
20

六个子数组分别是 `[1]`、`[2]`、`[3]`、`[1,2]`、`[2,3]`、`[1,2,3]`，和分别是 $1$、$2$、$3$、$3$、$5$、$6$，加起来是 $20$。

输入

```
3
-1 -2 -3

输出

```
-20

全是负数时答案为负，不能初始化为 $0$。

#### 题目分析

把本章例一写成标准输入输出，是贡献法最干净的入门：**不枚举区间，改成问「每个元素被多少个区间算到」**。

下标从 $1$ 开始，$a_i$ 被包含，当且仅当左端点落在 $1 \sim i$、右端点落在 $i \sim n$。左端点 $i$ 种选法、右端点 $n - i + 1$ 种，所以

$$\text{答案} = \sum_{i=1}^{n} a_i \times i \times (n - i + 1)$$

一遍循环，$O(n)$。对比枚举左右端点的 $O(n^2)$，这就是本章开头说的「降一个量级」。

**两个必须注意的点：**

- **乘积要用 `long long`。** $n = 10^5$ 时 $i \times (n - i + 1)$ 最大约 $2.5 \times 10^9$，已经越过 `int` 上限（约 $2.1 \times 10^9$）。代码里写 `x * 1LL * i * (n - i + 1)`，把 `1LL` 放在最前面让整条表达式提升到 64 位——这是本章易错点第一条。
- **`ans` 要允许负数。** 第二个样例全是负数，答案 $-20$。贡献次数恒为正，符号完全来自 $a_i$ 本身，所以初值写 $0$ 是对的，但绝不能因为「看起来像求和」就把它当成非负的量去用无符号类型。

还有一个容易忽略的点：这题**不需要前缀和**。看到「子数组求和」很多人第一反应是预处理前缀和，但前缀和优化的是「多次询问区间和」，而本题一次也不询问——直接数贡献次数就够了。用前缀和反而是 $O(n^2)$（枚举所有区间再 $O(1)$ 查询），仍然超时。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 2：所有数对的异或和之和

在线评测练习：[P1518 所有数对的异或和之和](https://dailyup.run/tasks/602)

#### 题目描述

给定 $n$ 个非负整数，求所有满足 $i < j$ 的数对 $(i, j)$ 的异或值 $a_i \oplus a_j$ 之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有数对异或值的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $0 \le a_i < 2^{20}$。

#### 输入输出样例

输入

```
3
1 2 3

输出

```
6

三个数对：$1 \oplus 2 = 3$、$1 \oplus 3 = 2$、$2 \oplus 3 = 1$，加起来是 $6$。

输入

```
2
0 0

输出

```
0

#### 题目分析

数对有 $O(n^2)$ 个，直接枚举就超时。破局点是本章例二、例四讲的那条通用套路：**按位拆开，每一位独立统计**。

异或的性质正好适合拆位：**第 $b$ 位的结果只取决于两个数在这一位是否相同**，与其它位无关。所以

$$\text{答案} = \sum_{b=0}^{19} 2^b \times (\text{第 } b \text{ 位为 1 的数对个数})$$

设第 $b$ 位为 1 的数有 $c_1$ 个、为 0 的有 $c_0 = n - c_1$ 个。要让异或在这一位为 1，必须「一 1 一 0」，方案数就是

$$c_1 \times c_0$$

这就是**贡献法的第二次换角度**：从「枚举数对」换成「数清这一位的 0 和 1」——不再关心具体是哪两个数，只关心它们的个数。

**细节：**

- **上界是 20 位。** 题目保证 $a_i < 2^{20}$，所以第 $0$ 位到第 $19$ 位遍历即可。本章例二写的 `b < 31` 是针对 `int` 全范围，这里按题目给的范围收窄更严谨。多写几位不会错（贡献为 0），少写就会漏答案。
- **`1LL << b` 而不是 `1 << b`。** $b = 19$ 时 $1 \ll 19$ 还在 `int` 内，但和前面的计数相乘就溢出了，所以移位字面量也要用 64 位。
- **答案量级。** 最大约 $\frac{n(n-1)}{2} \times 2^{20} \approx 5 \times 10^{15}$，`long long` 才装得下。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 3：所有子数组的最大值之和

在线评测练习：[P1520 所有子数组的最大值之和](https://dailyup.run/tasks/604)

#### 题目描述

给定 $n$ 个整数，求它所有连续子数组的最大值之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有连续子数组最大值的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $|a_i| \le 10^6$。

#### 输入输出样例

输入

```
4
3 1 2 4

输出

```
30

$n=4$ 时子数组共 $4 \times 5 / 2 = 10$ 个，它们的最大值分别是：`[3]`$=3$、`[1]`$=1$、`[2]`$=2$、`[4]`$=4$、`[3,1]`$=3$、`[1,2]`$=2$、`[2,4]`$=4$、`[3,1,2]`$=3$、`[1,2,4]`$=4$、`[3,1,2,4]`$=4$，加起来是 $30$。

输入

```
3
5 5 5

输出

```
30

有重复值时也要正确计数：每个子数组的最大值都是 $5$，$n=3$ 时子数组共 $3 \times 4 / 2 = 6$ 个，总和 $30$。

#### 题目分析

这道题不能像练习 1 那样「每个元素乘固定次数」——$a_i$ 到底被算了几次，取决于它是不是所在区间里的最大值，而这和它左右两侧有没有更大的数相关。

贡献法的正确问法是：**「以 $a_i$ 为最大值」的子数组有多少个？** 答案乘上 $a_i$ 再累加。

设 $L$ 是 $i$ 左边第一个**严格大于** $a_i$ 的位置，$R$ 是 $i$ 右边第一个**大于等于** $a_i$ 的位置。那么左端点可以在 $L+1 \sim i$ 里选、右端点可以在 $i \sim R-1$ 里选，个数就是

$$(i - L) \times (R - i)$$

$L$、$R$ 用**单调栈**在 $O(n)$ 内全部求出——这正是本章小结里「要求每个元素作为最大值的区间数，用单调栈求左右边界」那条。

**为什么两边一个严格、一个非严格？** 这是本章易错点里专门列的一条。假设数组是 `5 5`：如果两边都用「严格大于」作界，那么对第 1 个 5，右边没有严格大于它的，$R = 3$，它被算在 `[5]`、`[5,5]` 两个区间里；对第 2 个 5，$L = 0$、$R = 3$，它也被算在 `[5]`、`[5,5]` 两个区间里。同一个区间 `[5,5]` 被两个位置各认领一次，最大值之和就多算了一遍。

把右边改成「大于等于」作界，第 1 个 5 的 $R$ 就变成 2（第 2 个 5 是「大于等于」它的），它只管 `[5]`；第 2 个 5 管 `[5,5]` 和它自己。每个子数组恰好被认领一次。

第二个样例 `5 5 5` 就是专门检查这一点的：正确总和 $30$（6 个子数组最大值都是 5）。如果两边都用严格，会算出 $45$。

**细节：**

- `L[i]` 没有更大值时记 $0$，`R[i]` 没有更大值时记 $n+1$，这样 `i - L[i]` 和 `R[i] - i` 直接就是合法个数，不需要特判。
- 单调栈的实现里，求 $L$ 是从左往右扫、栈内**递减**；求 $R$ 是从右往左扫、栈内**递增**。两次扫描之间要清空栈。
- `a[i] * 1LL * (i - L[i]) * (R[i] - i)` 要用 `long long`：$|a_i| \le 10^6$、区间数最多约 $2.5 \times 10^9$，乘积到 $10^{15}$ 量级。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 4：所有数对的距离之和

在线评测练习：[P1516 所有数对的距离之和](https://dailyup.run/tasks/600)

#### 题目描述

给定 $n$ 个整数，求所有满足 $i < j$ 的数对的 $|a_i - a_j|$ 之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有数对差的绝对值之和。

#### 数据范围

- $1 \le n \le 10^5$。
- $|a_i| \le 10^6$。

#### 输入输出样例

输入

```
4
1 3 2 4

输出

```
10

数对之差分别是 $2$、$1$、$3$、$1$、$2$、$1$，加起来是 $10$。

输入

```
2
-1000000 1000000

输出

```
2000000

#### 题目分析

绝对值破坏了「按位拆」这条路（绝对值不是位运算），但贡献法仍然好用——只要**先排序把绝对值拆掉**。

排好序之后 $a_0 \le a_1 \le \cdots \le a_{n-1}$，于是对任意 $i < j$ 都有 $|a_i - a_j| = a_j - a_i$，绝对值自然消失。

现在用贡献法：$a_i$ 会出现在哪些数对的差里，各自是加还是减？

- 它比**前面**的 $i$ 个数都大，所以在这些数对里它是**被减数**，贡献 $+a_i$，共 $i$ 次；
- 它比**后面**的 $n-1-i$ 个数都小，所以在这些数对里它是**减数**，贡献 $-a_i$，共 $n-1-i$ 次。

合并起来，$a_i$ 的净贡献是

$$a_i \times \bigl(i - (n - 1 - i)\bigr) = a_i \times (2i - n + 1)$$

累加即可。排序 $O(n \log n)$ 主导复杂度。

**这条是本章小结里的那句「数对型问题（异或和、差的绝对值和）也可以用贡献法，常常先排序或按位拆」的具体落地**：两道数对题走了两条不同的路——异或和按位拆，绝对差先排序。

**细节：**

- **排序之后原来的下标顺序就没了**，所以必须先读完整份数据再排序。本题不要求按下标输出，所以没有影响；如果题目还要原始的 $i < j$ 关系，那就不能这么排（不过差的绝对值本身与下标无关，所以安全）。
- **系数可能为负**，`2i - n + 1` 在 $i$ 较小的时候是负数。这正是它表达「作减数的次数多于作被减数」的方式，不要去 `abs` 它。
- **`2LL * i` 而不是 `2 * i`**：$i$ 到 $10^5$ 时 $2i$ 还不溢出，但和 `a[i]` 相乘前必须确保整体是 64 位运算。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 5：所有数对的按位与之和

在线评测练习：[P1514 所有数对的按位与之和](https://dailyup.run/tasks/598)

#### 题目描述

给定 $n$ 个非负整数，求所有满足 $i < j$ 的数对的按位与之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有数对按位与的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $0 \le a_i < 2^{20}$。

#### 输入输出样例

输入

```
3
1 2 3

输出

```
3

$1 \mathbin{\&} 2 = 0$、$1 \mathbin{\&} 3 = 1$、$2 \mathbin{\&} 3 = 2$，加起来是 $3$。

输入

```
3
0 0 0

输出

```
0

#### 题目分析

和练习 2 同一套框架——**按位拆、数清这一位的 1、算方案数**——区别只在「什么样的数对能让这一位变成 1」。

| 运算 | 第 $b$ 位结果为 1 的条件 | 方案数 |
| --- | --- | --- |
| 异或 | 两个数这一位**不同** | $c_1 \times c_0$ |
| 与 | 两个数这一位**都是 1** | $\dbinom{c_1}{2} = \dfrac{c_1(c_1-1)}{2}$ |

「与」要求两个数都是 1，所以是从 $c_1$ 个里任取两个，即 $\binom{c_1}{2}$。**这就是复习里那张表在本章的第一次落地**，和练习 2 对着记，两题的代码结构完全一样，只有一行公式不同。

**细节：**

- **`c1 * (c1 - 1) / 2` 必须 `long long`。** $c_1$ 到 $10^5$ 时乘积到 $10^{10}$，`int` 早就溢出。因为 `c1` 已声明为 `long long`，这里自然安全。
- **先乘后除。** 写成 `c1 * (c1 - 1) / 2` 是对的（$c_1(c_1-1)$ 一定是偶数，且中间值在 64 位内）；写成 `c1 / 2 * (c1 - 1)` 也可以，但 `/2` 放在前面时要小心 $c_1$ 为奇数时整除的语义——虽然结果相同，可读性不如前者。
- **$c_1 < 2$ 时自然为 0**，不需要特判。第二个样例全是 0，每一位 $c_1 = 0$，答案 0。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 6：子数组的按位与之和

在线评测练习：[P1519 子数组的按位与之和](https://dailyup.run/tasks/603)

#### 题目描述

给定 $n$ 个非负整数，求它所有**连续子数组**的按位与之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有连续子数组按位与的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $0 \le a_i < 2^{20}$。

#### 输入输出样例

输入

```
3
1 2 3

输出

```
8

子数组共 $6$ 个：`[1]`$=1$、`[2]`$=2$、`[3]`$=3$、`[1,2]`$=0$、`[2,3]`$=2$、`[1,2,3]`$=0$，加起来是 $8$。

输入

```
3
5 5 5

输出

```
30

每个子数组的按位与都是 $5$，共 $6$ 个，总和 $30$。

#### 题目分析

**这道题和练习 4 的区别是本章最关键的易错点：统计对象从「数对」变成了「连续子数组」。**

- 练习 4 数的是**数对**：正好两个数，方案数是 $\binom{c_1}{2}$；
- 这道题数的是**子数组**：长度可以是 $1$ 到 $n$，方案数是把连续段累加。

两者都是「按位拆」，但**方案数公式完全不同，绝不能互相套用**——这正是易错点清单里「混用数对与子数组的公式」那一条。

按位看第 $b$ 位：一个子数组的与在这一位为 1，当且仅当**这个子数组里每个数在这一位都是 1**。也就是说，这个子数组必须整段落在「这一位全为 1 的连续段」里。

于是做法很自然：扫一遍数组，把这一位为 1 的位置连成一段段。一段长度 $len$ 里有 $\frac{len(len+1)}{2}$ 个连续子数组，全部累加就是这一位为 1 的子数组个数，再乘 $2^b$。

**这是本章例五的实现**，和下一题（按位或）构成镜像：

- **与**：数为 1 的段，直接累加（条件苛刻，正好是连续 1）；
- **或**：数为 0 的段，用「总数 −」（条件宽松，反着数更方便）。

**最容易漏的一行是「最后一段的结算」。** 循环结束时 `len` 里可能还存着一段的长度，如果只在遇到 0 时才结算，数组末尾那段就永远丢了。第二个样例 `5 5 5` 正是这种情况：所有位全是 1，`len` 从头累积到 3，一个 0 都没遇到，如果漏掉循环后的那一行，答案直接是 0。这也是本章易错点「分段统计漏掉最后一段」的典型翻车现场。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

### 练习 7（挑战）：子数组的按位或之和

在线评测练习：[P1515 子数组的按位或之和](https://dailyup.run/tasks/599)

#### 题目描述

给定 $n$ 个非负整数，求它所有**连续子数组**的按位或之和。

#### 输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数，相邻两个整数之间用一个空格隔开。

#### 输出格式

输出一个整数，表示所有连续子数组按位或的总和。

#### 数据范围

- $1 \le n \le 10^5$。
- $0 \le a_i < 2^{20}$。

#### 输入输出样例

输入

```
3
1 2 3

输出

```
15

子数组 $6$ 个，或值分别为 $1$、$2$、$3$、$3$、$3$、$3$，加起来是 $15$。

输入

```
3
0 0 0

输出

```
0

#### 题目分析

这是本章例二的完整实现，放在最后是为了和练习 5 形成**完整对照**。

按位看第 $b$ 位：一个子数组的或在这一位为 1，当且仅当**这个子数组里至少有一个数在这一位是 1**。

「至少一个」不好直接数（要数「有 1 个 1 的、2 个 1 的、……」），于是用本章那条思维定式：**反着数**。

$$\text{这一位为 1 的子数组数} = \text{子数组总数} - \text{这一位全为 0 的子数组数}$$

子数组总数是 $\frac{n(n+1)}{2}$；全为 0 的子数组数，就是把这一位为 0 的位置切成连续段，每段长度 $len$ 贡献 $\frac{len(len+1)}{2}$，累加起来。两者相减再乘 $2^b$。

**和练习 5 对照着读，能看出本章那句「或统计 1 的补集、与统计 1 本身」的由来：**

| 统计对象 | 运算 | 为 1 的条件 | 做法 |
| --- | --- | --- | --- |
| 数对 | 异或 | 两数不同 | $c_1 \times c_0$ |
| 数对 | 与 | 两数都是 1 | $\dbinom{c_1}{2}$ |
| 子数组 | 与 | 全是 1 | 数**全 1 段**，$\sum \frac{len(len+1)}{2}$ |
| 子数组 | 或 | 至少一个 1 | 总数 − 数**全 0 段** |

**同样别忘了最后一段。** 第二个样例全是 0，如果漏掉循环后的结算，全零段数会被算成 0，「总数 − 0」就等于总数，答案会错得很大——反而比练习 5 的漏算更隐蔽。

另外注意 `total` 要用 `1LL * n * (n + 1) / 2` 算：$n = 10^5$ 时约 $5 \times 10^9$，`int` 装不下。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/contribution/index.md

## 小结

贡献法的核心是**换一个统计单位**：不去枚举每个区间，而是统计每个元素参与了哪些区间。

它适用的信号很明确：题目要求「所有子区间的某个量之和」，而逐个区间算又是 $O(n^2)$ 以上。

- 元素 $a_i$（1-based）出现在 $i \times (n - i + 1)$ 个连续子数组里。
- 涉及位运算时，把每一位拆开，各自独立统计再合并。
- 要求「每个元素作为最大值（或最小值）的区间数」，用单调栈求左右边界。
- 数对型问题（异或和、差的绝对值和）也可以用贡献法，常常先排序或按位拆。
- 乘积累加一律用 `long long`。

学完这一章，下面这些事应该能独立完成：

- 说出贡献法与「枚举左右端点」的区别，并写出子数组和之和的 $O(n)$ 解法。
- 把异或和、或和、与和这类问题按位拆开，推导出每一位的贡献公式。
- 写出单调栈求「左边第一个严格大于、右边第一个大于等于」的代码，并说清为什么要一边严格。
- 对排序后的数组，说出 $a_i$ 在「差的绝对值之和」里被算了多少次。
- 分清「数对」与「连续子数组」两类统计对象：前者按 $\binom{c}{2}$ 或 $c_1 c_0$ 算方案，后者要对连续段累加 $\frac{len(len+1)}{2}$。
- 记住四种按位组合的公式（数对异或/与、子数组与/或），并能说出「与数全 1 段、或数全 0 段」的原因。
- 写出分段统计时不忘「最后一段要单独结算」。

Source: https://cppguide.xyz/algopatterns/contribution/index.mdx
