当前位置：首页 > news >正文

（新）01前缀和来临！优点多多！

news 2025/2/23 13:15:06

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

新年快乐！！！

1.引，01前缀和的登场

2. 01前缀和的自我展示

2.1.我的出现

2.2.我的概念是？

2.3.如何和我交盆友？

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

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

3.2.我的特长（应用）

示例应用场景

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

4.1.新二进制

4.1.1题目

题目描述

输入格式

输出格式

数据范围

样例数据

4.1.2.思路

4.1.3.代码

5.总结

1.引，01前缀和的登场

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

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

2. 01前缀和的自我展示

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

2.1.我的出现

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

2.2.我的概念是？

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

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

2.3.如何和我交盆友？

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)

说明：

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

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

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
通过二进制前缀和可以快速判断某个子数组是否全为1，只需比较该区间的1的个数是否等于子数组的长度。

解决类似“最长连续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.思路

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