做网站 需要工信部备案吗,php网站开发学习,怎么建立网站 个人,响应式网站怎么做才实用个人主页#xff1a;PingdiGuo_guo 收录专栏#xff1a;C干货专栏 【PingdiGuo_guo#xff1a;一名C、数据结构、算法等爱好者#xff0c;用所学帮助大家#xff0c;感谢关注#xff01;】 新年刚过#xff0c;在这里先祝各位 新年快乐#xff01;#xff01;#xf… 个人主页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)11112231 XOR 2 3336(1 XOR 2) XOR 3 04410 (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相同数字异或结果为 0a XOR 0 a0 异或任何数结果为该数a XOR b b XOR a交换律 计算过程 位置 10 (初始值) XOR 1 1。位置 21 XOR 2 3。位置 33 XOR 3 0。位置 40 XOR 4 4注意其实01前缀和就是异或前一个的结果只不过符号变了。 据说图像更能帮助记忆不知道这个图像文字说明 能不能更好帮助大家记住。
01前缀和又到了我的时间既然大家都明白我的过程了老话说看会和做会是两码事。那么就让PingdiGuo_guo用C和Python代码来演示一下吧请看~~~憨憨音
C代码
#includebits/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(i1;i3;i)//普通前缀和演示过程,注意i从2开始{s[i]a[i]s[i-1];//加上前一个couts[i] ;}cout\n01 t[0] ;for(i1;i3;i)//01前缀和过程{t[i]t[i-1]^a[i];//异或^coutt[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相同 2.3.2.我的用法
1. 单点和 单点和是指数组中某一个元素的值。使用异或运算的前缀和可以用来快速计算区间和但单点和本身不需要前缀和的支持可以直接从数组中获取。 语言解释 单点和是从数组中直接访问某一个元素的值。 异或运算的前缀和主要用于计算区间和单点和可以直接通过数组索引访问。 代码片段
vectorint arr {1, 2, 3, 4, 5};
int singlePoint arr[2]; // 访问第三个元素索引为2
2.区间和 区间和是指数组中某一段区间 [l, r] 内所有元素的累加和。使用异或运算的前缀和可以快速计算区间和。 语言解释 使用异或运算的前缀和数组 prefix其中 prefix[i] 表示从数组起点到第 i 个元素的异或结果。 区间和可以通过 prefix[r] ^ prefix[l-1] 计算前提是数组中元素的异或满足结合律。 代码片段
vectorint arr {1, 2, 3, 4, 5};
vectorint prefix(arr.size() 1, 0);
prefix[0] 0;
for (int i 0; i arr.size(); i) {prefix[i1] prefix[i] ^ arr[i];
}
int l 1, r 3; // 区间[1,3]1-based索引
int intervalSum prefix[r] ^ prefix[l-1]; // 区间和为6
3. 区间最值 区间最值指的是数组中某一段区间 [l, r] 内的最大值或最小值。使用异或运算的前缀和可以辅助计算区间最值。 语言解释 异或运算的前缀和可以用于快速计算区间和但区间最值需要遍历区间内的所有元素。 通过预处理数组的最大值和最小值可以在常数时间内查询区间最值。 代码片段
vectorint 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 个元素的异或结果。 预处理后可以通过简单计算得到区间和。 代码片段
vectorint arr {1, 2, 3, 4, 5};
vectorint prefix(arr.size() 1, 0);
prefix[0] 0;
for (int i 0; i arr.size(); i) {prefix[i1] prefix[i] ^ arr[i];
}
5. 差分 差分数组用于处理区间更新和单点查询的问题。使用异或运算的前缀和可以辅助实现差分数组。 语言解释 使用异或运算的差分数组 diff其中 diff[l] ^ value 和 diff[r1] ^ value 表示对区间 [l, r] 进行更新。 预处理后可以通过遍历 diff 数组得到更新后的数组。 代码片段
vectorint arr {1, 2, 3, 4, 5};
vectorint diff(arr.size() 2, 0);
int l 1, r 3, value 10; // 更新区间[1,3]1-based索引
diff[l] ^ value;
diff[r1] ^ 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) 的异或结果。 多维前缀和可以用于快速计算矩形区域的异或结果。 代码片段
vectorvectorint arr {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vectorvectorint prefix(arr.size() 1, vectorint(arr[0].size() 1, 0));for (int i 0; i arr.size(); i) {for (int j 0; j arr[0].size(); j) {prefix[i1][j1] prefix[i1][j] ^ prefix[i][j1] ^ prefix[i][j];prefix[i1][j1] ^ 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[r11][r21] ^ prefix[l1-1][r21] ^ prefix[r11][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 通过二进制前缀和可以快速判断某个子数组是否全为1只需比较该区间的1的个数是否等于子数组的长度。 解决类似“最长连续1”的问题 通过二进制前缀和可以快速找到最长连续1的子数组。 总之二进制前缀和是一种高效的工具能够帮助解决二进制数组相关的计数和查询问题。
4.我的帮助例子题目
4.1.新二进制
4.1.1题目 内存限制: 512 Mb时间限制: 1000 ms 题目描述 Bob 最近正在学习二进制但二进制的每一位上只能是 00 或 11这让 Bob 觉得很无趣于是他研究出了一种新的二进制每一位上只能是 −1−1 或 11 Bob 想研究的新二进制数有 nn 位它可以表示为 b1×20b2×21⋯bn×2n−1b1×20b2×21⋯bn×2n−1其中 bibi 等于 ±1±1。进一步地Bob 认为一个区间 [l,r][l,r] 满足 1≤l≤r≤n1≤l≤r≤n 是正的当且仅当其代表值 bl×2l−1bl1×2l⋯br×2r−10bl×2l−1bl1×2l⋯br×2r−10区间 [l,r][l,r] 是负的则表示代表值 00。 请问正区间个数和负区间个数相差多少换言之将正区间的个数记为 AA负区间的个数记为 BB求 ∣A−B∣∣A−B∣ 的值。 输入格式 第一行一个整数 TT 表示数据组数对于每组数据 第一行一个整数 nn。 第二行 nn 个整数 b1∼nb1∼n。 输出格式 对于每组数据输出一行一个整数表示答案。 数据范围 对于 30%30% 的数据1≤T≤101≤T≤101≤n≤501≤n≤50。 对于 60%60% 的数据1≤T≤101≤T≤101≤n≤10001≤n≤1000。 对于 100%100% 的数据1≤T≤1051≤T≤1051≤n≤1051≤n≤105∑n≤3×105∑n≤3×105bi1bi1 或 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则A1,B2,|A-B|1。 4.1.2.思路 前缀和数组我们定义一个前缀和数组 S其中 S[i] 表示从第一个元素到第i个元素的和。这样区间 [l, r] 的值可以表示为 S[r] - S[l-1]。维护有序列表我们维护一个有序列表来记录已经处理过的前缀和值。对于每个新的前缀和值我们使用二分查找来统计有多少个已经处理过的值小于当前值这样可以快速确定正区间的数量。计算结果总区间数为 n*(n1)/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;}
};// vectorNode sortedSet用于维护有序的集合
vectorNode 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;vectorint b(n); // 输入数组for (int i 0; i n; i) {cin b[i];}// 计算前缀和数组Svectorint 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前缀和的一遍博客希望对大家有帮助也希望大家给个赞制作不易谢谢
