【C++编程探索】01前缀和来临！优点多多！八千字详解

个人主页：PingdiGuo_guo

收录专栏：C++干货专栏

【PingdiGuo_guo：一名C++、数据结构、算法等爱好者，用所学帮助大家，感谢关注！】

新年刚过，在这里先祝各位

新年快乐！！！

1.引，01前缀和的登场

俗活说“新年新气象”，我们也要努力做题了，但有一道前缀和的题，PingdiGuo_guo却遇到了问题，原因是：普通的前缀和解法太慢了，导致超时问题。为避免大家踩坑（PingdiGuo_guo也顺便了解一下），我特地查了一下，发现有一种好的前缀和——

01前缀和！！！（当当啷当）

目录

1.引，01前缀和的登场

2. 01前缀和的自我展示

2.1.我的出现

2.2.我的概念是？

2.3.如何和我交盆友？

2.3.1.我的样子

2.3.2.我的用法

3.关于我的番外（其他）

3.1.我与亲戚（普通前缀和）的区别？

3.2.我的特长（应用）

示例应用场景

4.我的帮助例子（题目）

4.1.新二进制

4.1.1题目

题目描述

输入格式

输出格式

数据范围

样例数据

4.1.2.思路

4.1.3.代码

5.总结

---

2. 01前缀和的自我展示

Hello everyone! 我是01前缀和（憨憨音），PingdiGuo_guo邀请我来他的博客，那么各位，接下来我要自我介绍了哈！

2.1.我的出现

哲学家黑格尔说“理性存在，即为合理”，没错，我提高了普通前缀和的效率，即便普通前缀和能应对大多数情况，但也有例外（比如PingdiGuo_guo的题，嘿嘿），这时候我就上场啦！

2.2.我的概念是？

前缀和大家应该都熟悉（就是把前一项累加），我是一种前缀和家族的特殊一员，通常用于处理二进制数据或特定状态的累积问题。

PingdiGuo_guo：与常见的前缀和不同，它的计算基于二进制位的0和1，适用于处理类似开关状态、二进制掩码或位运算等问题。

2.3.如何和我交盆友？

2.3.1.我的样子

PingdiGuo_guo：为了方便大家了解，我现在给大家用常用工具Excel表格演示一下，（如表）。

假设有一个十进制数组 A：

位置	数组 A	普通前缀和	01 前缀和 (使用 XOR)
1	1	1	1
2	2	3	1 XOR 2 = 3
3	3	6	(1 XOR 2) XOR 3 = 0
4	4	10	(1 XOR 2 XOR 3) XOR 4 =4

避免大家混淆，来点说明：

1.普通前缀和：从第一个元素开始，逐步累加所有元素的值。

• 例如，位置 2 的普通前缀和是 1 + 2 = 3，位置 3 的普通前缀和是 1 + 2 + 3 = 6。

2.01 前缀和（使用 XOR）：使用二进制运算中的异或（XOR）操作来计算前缀和。

• XOR 运算规则：
  • a XOR a = 0（相同数字异或结果为 0）
  • a XOR 0 = a（0 异或任何数结果为该数）
  • a XOR b = b XOR a（交换律）
• 计算过程：
  • 位置 1：0 (初始值) XOR 1 = 1。
  • 位置 2：1 XOR 2 = 3。
  • 位置 3：3 XOR 3 = 0。
  • 位置 4：0 XOR 4 = 4
  • 注意：其实01前缀和就是异或前一个的结果，只不过符号变了。

据说图像更能帮助记忆，不知道这个（图像+文字说明  能不能更好帮助大家记住。

01前缀和：又到了我的时间，既然大家都明白我的过程了，老话说：看会和做会是两码事。那么就让PingdiGuo_guo用C++和Python代码来演示一下吧！请看~~~（憨憨音）

C++代码：

#include<bits/stdc++.h>//万能头文件
using namespace std;
int a[20]={1,2,3,4};
int s[20],t[20];//s数组代表普通的前缀和，t数组代表01前缀和
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int i;//循环变量s[0]=t[0]=a[0];//特殊处理：第一个cout<<"普通： "<<s[0]<<' ';for(i=1;i<=3;i++)//普通前缀和演示过程,注意i从2开始{s[i]=a[i]+s[i-1];//加上前一个cout<<s[i]<<' ';}cout<<'\n'<<"01： "<<t[0]<<' ';for(i=1;i<=3;i++)//01前缀和过程{t[i]=t[i-1]^a[i];//异或：^cout<<t[i]<<' ';}return 0;
}

C++代码运行结果：

Python代码：

a = [1, 2, 3, 4]
s = [0] * len(a)
t = [0] * len(a)# 初始化s数组（普通前缀和）
s[0] = a[0]
for i in range(1, len(a)):s[i] = s[i-1] + a[i]# 初始化t数组（01前缀和）
t[0] = a[0]
for i in range(1, len(a)):t[i] = t[i-1] ^ a[i]print("普通前缀和：", end=" ")
print(s)
print("01前缀和：", end=" ")
print(t)

说明：

1. 初始化数组a
2. 分别计算普通前缀和s和01前缀和t
3. 输出结果（与C++相同）

2.3.2.我的用法

1. 单点和

单点和是指数组中某一个元素的值。使用异或运算的前缀和可以用来快速计算区间和，但单点和本身不需要前缀和的支持，可以直接从数组中获取。

语言解释：

单点和是从数组中直接访问某一个元素的值。
异或运算的前缀和主要用于计算区间和，单点和可以直接通过数组索引访问。

代码片段：

vector<int> arr = {1, 2, 3, 4, 5};
int singlePoint = arr[2]; // 访问第三个元素（索引为2）

2.区间和

区间和是指数组中某一段区间 [l, r] 内所有元素的累加和。使用异或运算的前缀和可以快速计算区间和。

语言解释：

使用异或运算的前缀和数组 prefix，其中 prefix[i] 表示从数组起点到第 i 个元素的异或结果。
区间和可以通过 prefix[r] ^ prefix[l-1] 计算，前提是数组中元素的异或满足结合律。

代码片段：

vector<int> arr = {1, 2, 3, 4, 5};
vector<int> prefix(arr.size() + 1, 0);
prefix[0] = 0;
for (int i = 0; i < arr.size(); ++i) {prefix[i+1] = prefix[i] ^ arr[i];
}
int l = 1, r = 3; // 区间[1,3]（1-based索引）
int intervalSum = prefix[r] ^ prefix[l-1]; // 区间和为6

3. 区间最值

区间最值指的是数组中某一段区间 [l, r] 内的最大值或最小值。使用异或运算的前缀和可以辅助计算区间最值。

语言解释：

异或运算的前缀和可以用于快速计算区间和，但区间最值需要遍历区间内的所有元素。
通过预处理数组的最大值和最小值，可以在常数时间内查询区间最值。

代码片段：

vector<int> arr = {1, 2, 3, 4, 5};
int l = 1, r = 3; // 区间[1,3]（1-based索引）
int minVal = *min_element(arr.begin() + l - 1, arr.begin() + r);
int maxVal = *max_element(arr.begin() + l - 1, arr.begin() + r);

4. 数组预处理

数组预处理指对数组进行某种形式的预处理，以便后续操作更快。使用异或运算的前缀和可以用于数组预处理。

语言解释：

使用异或运算的前缀和数组 prefix，其中 prefix[i] 表示从数组起点到第 i 个元素的异或结果。
预处理后，可以通过简单计算得到区间和。

代码片段：

vector<int> arr = {1, 2, 3, 4, 5};
vector<int> prefix(arr.size() + 1, 0);
prefix[0] = 0;
for (int i = 0; i < arr.size(); ++i) {prefix[i+1] = prefix[i] ^ arr[i];
}

5. 差分

差分数组用于处理区间更新和单点查询的问题。使用异或运算的前缀和可以辅助实现差分数组。

语言解释：

使用异或运算的差分数组 diff，其中 diff[l] ^= value 和 diff[r+1] ^= value 表示对区间 [l, r] 进行更新。
预处理后，可以通过遍历 diff 数组得到更新后的数组。

代码片段：

vector<int> arr = {1, 2, 3, 4, 5};
vector<int> diff(arr.size() + 2, 0);
int l = 1, r = 3, value = 10; // 更新区间[1,3]（1-based索引）
diff[l] ^= value;
diff[r+1] ^= value;// 应用差分
for (int i = 1; i < diff.size(); ++i) {diff[i] ^= diff[i-1];
}// 输出结果
for (int i = 1; i < arr.size(); ++i) {arr[i] ^= diff[i];
}

6. 多维和

多维和指的是对二维或更高维数组进行前缀和计算。使用异或运算的前缀和可以用于多维数组的处理。

语言解释：

对二维数组 arr，使用异或运算的前缀和 prefix，其中 prefix[i][j] 表示从起点到 (i,j) 的异或结果。
多维前缀和可以用于快速计算矩形区域的异或结果。

代码片段：

vector<vector<int>> arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vector<vector<int>> prefix(arr.size() + 1, vector<int>(arr[0].size() + 1, 0));for (int i = 0; i < arr.size(); ++i) {for (int j = 0; j < arr[0].size(); ++j) {prefix[i+1][j+1] = prefix[i+1][j] ^ prefix[i][j+1] ^ prefix[i][j];prefix[i+1][j+1] ^= arr[i][j];}
}// 计算矩形区域[l1, r1] x [l2, r2]的异或结果
int l1 = 1, r1 = 2; // 1-based行索引
int l2 = 1, r2 = 2; // 1-based列索引
int result = prefix[r1+1][r2+1] ^ prefix[l1-1][r2+1] ^ prefix[r1+1][l2-1] ^ prefix[l1-1][l2-1];

怎么样，大家明白我的用法了吗？

3.关于我的番外（其他）

3.1.我与亲戚（普通前缀和）的区别？

区别有以下几点：

1. 普通前缀和

• 定义：数组中从第一个元素到第i个元素的所有元素的和。
• 适用场景：用于计算任意子数组的和，适用于元素可以是任意整数的情况。
• 计算方式：通过累加数组中的每个元素的值来计算前缀和。
• 优点：计算简单，适用于元素范围广泛的场景。
• 缺点：不适用于二进制数组的特定操作（如统计1的个数）。

---

2. 01前缀和（二进制前缀和）

• 定义：数组中从第一个元素到第i个元素的所有元素的二进制异或（XOR）结果。
• 适用场景：用于处理二进制数组，快速计算子数组的异或结果。
• 计算方式：通过累加（异或操作）数组中的每个元素的值来计算前缀和。
• 优点：特别适用于处理二进制数组，如统计1的个数、查找特定子数组的异或结果等。
• 缺点：不适用于一般整数数组的和计算。

汇总一下，如表：

项目	普通前缀和	01前缀和（二进制前缀和）
定义	数组中从第一个元素到第i个元素的和	数组中从第一个元素到第i个元素的异或（XOR）结果
适用场景	适用于计算任意子数组的和，元素是整数	适用于处理二进制数组，计算子数组的异或结果
计算方式	通过累加数组元素的值	通过累加（异或操作）数组元素的值
优点	简单易懂，适用于元素范围广泛的场景	特别适用于二进制数组的快速计算
缺点	不适用于二进制数组的特定操作（如统计1的个数）	无显著缺点，但不适用于一般整数数组的和计算

总结一下，大家在使用时记得注意区分，数据大，速度快时就用01前缀和，否则就用普通前缀和。（不要混淆呦~~多看几遍）。

3.2.我的特长（应用）

01（二进制前缀和（Bitwise Prefix Sum）主要用于处理二进制数组（由0和1组成的数组）中的前缀和问题。以下是其主要的应用场景和用途：

项目	描述
快速计算区间内1的个数	通过二进制前缀和可以快速计算数组中某区间内1的个数，避免了每次都遍历子数组的时间开销。
处理二进制数组的特定问题	例如，快速查找满足条件的子数组（如连续1的长度、特定模式的子数组等）。
高效前缀和查询	在需要频繁查询前缀和的场景中，二进制前缀和可以提供高效（O(1)时间复杂度）的查询方式。
相关算法优化	二进制前缀和常用于优化一些算法，例如模式匹配、滑动窗口等，减少时间复杂度。

示例应用场景

1. 统计特定区间的1的个数
   给定一个二进制数组，可以预先计算二进制前缀和数组，然后通过前缀和快速求出任意区间的1的个数。

2. 快速判断子数组是否全为1
   通过二进制前缀和可以快速判断某个子数组是否全为1，只需比较该区间的1的个数是否等于子数组的长度。

3. 解决类似“最长连续1”的问题
   通过二进制前缀和可以快速找到最长连续1的子数组。

总之，二进制前缀和是一种高效的工具，能够帮助解决二进制数组相关的计数和查询问题。

4.我的帮助例子（题目）

4.1.新二进制

4.1.1题目

内存限制: 512 Mb时间限制: 1000 ms

题目描述

Bob 最近正在学习二进制，但二进制的每一位上只能是 00 或 11，这让 Bob 觉得很无趣，于是他研究出了一种新的二进制：每一位上只能是 −1−1 或 11！

Bob 想研究的新二进制数有 nn 位，它可以表示为 b1×20+b2×21+⋯+bn×2n−1b1​×20+b2​×21+⋯+bn​×2n−1，其中 bibi​ 等于 ±1±1。进一步地，Bob 认为一个区间 [l,r][l,r] 满足 1≤l≤r≤n1≤l≤r≤n 是正的，当且仅当其代表值 bl×2l−1+bl+1×2l+⋯+br×2r−1>0bl​×2l−1+bl+1​×2l+⋯+br​×2r−1>0，区间 [l,r][l,r] 是负的则表示代表值 <0<0。

请问正区间个数和负区间个数相差多少？换言之，将正区间的个数记为 AA，负区间的个数记为 BB，求 ∣A−B∣∣A−B∣ 的值。

输入格式

第一行一个整数 TT 表示数据组数，对于每组数据：

第一行一个整数 nn。

第二行 nn 个整数 b1∼nb1∼n​。

输出格式

对于每组数据，输出一行一个整数表示答案。

数据范围

对于 30%30% 的数据，1≤T≤101≤T≤10，1≤n≤501≤n≤50。

对于 60%60% 的数据，1≤T≤101≤T≤10，1≤n≤10001≤n≤1000。

对于 100%100% 的数据，1≤T≤1051≤T≤105，1≤n≤1051≤n≤105，∑n≤3×105∑n≤3×105，bi=1bi​=1 或 bi=−1bi​=−1。

样例数据

输入:

4
4
1 -1 1 1
3
-1 -1 -1
2
1 -1
2
1 1

输出:

6
6
1
3

说明:

样例解释：对于第三组数据，区间 [1,1],[1,2],[2,2] 的代表值分别为 1,-1,-2，则A=1,B=2,|A-B|=1。

4.1.2.思路

1. 前缀和数组：我们定义一个前缀和数组 S，其中 S[i] 表示从第一个元素到第i个元素的和。这样，区间 [l, r] 的值可以表示为 S[r] - S[l-1]。
2. 维护有序列表：我们维护一个有序列表来记录已经处理过的前缀和值。对于每个新的前缀和值，我们使用二分查找来统计有多少个已经处理过的值小于当前值，这样可以快速确定正区间的数量。
3. 计算结果：总区间数为 n*(n+1)/2。正区间数减去负区间数的绝对值即为结果。

4.1.3.代码

C++：

#include <bits/stdc++.h>
using namespace std;// 结构体Node用于表示有序集合中的元素，每个节点存储一个值和该值出现的次数
struct Node {int value;int count;Node(int v) : value(v), count(1) {}Node(int v, int c) : value(v), count(c) {}bool operator<(const Node& other) const {return value < other.value;}
};// vector<Node> sortedSet用于维护有序的集合
vector<Node> sortedSet;// 插入新的前缀和值到有序集合中
void insertNode(int s) {// 使用lower_bound找到插入位置auto it = lower_bound(sortedSet.begin(), sortedSet.end(), s);if (it != sortedSet.end() && it->value == s) {// 如果已经存在该值，增加计数it->count += 1;return;}// 创建新的Node并插入Node temp(s, 1);sortedSet.insert(it, temp);
}// 统计小于等于目标值s的元素数量
int countLess(int s) {int count = 0;auto it = lower_bound(sortedSet.begin(), sortedSet.end(), s);return it - sortedSet.begin();
}int main() {int T;  // 测试用例的数量cin >> T;for (int case_num = 0; case_num < T; ++case_num) {int n;  // 数组的长度cin >> n;vector<int> b(n);  // 输入数组for (int i = 0; i < n; ++i) {cin >> b[i];}// 计算前缀和数组Svector<int> S(n + 1);S[0] = 0;for (int i = 1; i <= n; ++i) {int bit = 1 << (i - 1);  // 计算2^(i-1)S[i] = S[i - 1] + b[i - 1] * bit;}// 清理并初始化有序集合sortedSet.clear();sortedSet.push_back(Node(0, 1));  // 初始节点，表示前缀和为0的情况int positive = 0;  // 正区间数累计器for (int j = 1; j <= n; ++j) {int s = S[j];  // 当前前缀和positive += countLess(s);  // 统计小于等于s的前缀和数量insertNode(s);  // 插入当前前缀和到有序集合中}int total = n * (n + 1) / 2;  // 所有可能的区间数int negative = total - positive;  // 负区间数cout << abs(positive - negative) << endl;  // 输出结果}return 0;
}

Python：

import bisectdef compute_difference():import sysinput = sys.stdin.read().split()ptr = 0T = int(input[ptr])ptr += 1for _ in range(T):n = int(input[ptr])ptr += 1b = list(map(int, input[ptr:ptr + n]))ptr += nS = [0] * (n + 1)for i in range(1, n + 1):bit = 1 << (i - 1)S[i] = S[i - 1] + b[i - 1] * bitsorted_S = [S[0]]positive = 0for j in range(1, n + 1):s = S[j]cnt = bisect.bisect_left(sorted_S, s)positive += cntbisect.insort(sorted_S, s)total = n * (n + 1) // 2negative = total - positiveprint(abs(positive - negative))compute_difference()

5.总结

感谢各位帅哥美女的支持，以上是对01前缀和的一遍博客，希望对大家有帮助，也希望大家给个赞，制作不易，谢谢！