前缀和

发表于2026-01-31|更新于2026-02-07|算法学习枚举前缀和

|总字数:213|阅读时长:1分钟|浏览量:

这是求一个一维数组的前缀和
如果我们要计算4-9这个区间的和我们就可以用prefix[9]-prefix[3]得到

vector<int>prefix(n)
for(int i=0;i<n;i++)
{
	if(i)prefix[i]=prefix[i-1];
	prefix[i]+=arr[i];
}

异或的性质 :

核心定义：相同为 0，不同为 1(从位的角度)
任何数和 0 异或，结果还是它自己
A ^(B^C)=(A^B)^ C
自己异或自己 = 0
A=B ^ C,两边^ C,A^ C=B
求前缀异或
vector<int>prefix(n)
prefix[0]=arr[0]
for(int i=1;i<n;i++)
{
prefix[i]^=prefix[i-1];
}
如果我们要计算4-9这个区间的异或我们就可以用prefix[9]^ prefix[3]

二维前缀和(在二维矩阵中求任意子矩阵的和)

比如12就代表的是左上角2 * 2区域的和

文章作者: Zedward

文章链接: https://zedward-0417.github.io/2026/01/31/%E7%AE%97%E6%B3%95%E6%80%9D%E6%83%B3/9.%E5%89%8D%E7%BC%80%E5%92%8C/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Zedward'Blog！

相关推荐

题目描述给定 $n$ 个非负整数表示每个柱子的高度，每个柱子的宽度为 1，计算按此排列的柱子，下雨之后能接多少雨水。输入格式第一行包含一个整数 $n$，表示柱子的数量。接下来的 $n$ 行（或一行内），每行一个非负整数，表示每个位置柱子的高度 $height[i]$。输出格式输出一个整数，表示能够接住的雨水总量。对于每一个单位的我们只需要找到它左边的最大值和右边的最大值,取二者的最小值,再减去这个单位的柱子长度。用前缀最大值数组存储左边最大值,后缀最大值数组存储右边最大值#include<iostream>using namespace std;int main(){ int n,sum=0; cin>>n; int arr[n+1]; for(int i=1;i<=n;i++) cin>>arr[i]; int left_max[n+1]; int right_max[n+1]; for(int i=1;i<=n;i++) { if...

题目描述给定一个长度为$n$的数列$a_1, a_2, \dots, a_n$。每次可以选择一个区间$[l, r]$，使这个区间内的数都加 1 或者都减 1。请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。输入格式第一行一个正整数$n$。接下来$n$行，每行一个整数，第$i+1$行的整数表示$a_i$。输出格式第一行输出最少操作次数。第二行输出最终能得到多少种结果。输入输出样例 **输入 4 1 1 2 2 **输出 ``` 1 2 引言中有介绍如何得到最少的操作次数,对于最终得到的结果数:我们设正数和为p，负数和为q。在操作min(p,q)后只剩负数或者正数,这里假设只剩正数。我们还剩|p-q|次操作次数,在这每次操作中,区间一端必定在正数,另一端我们可以自由选择在哪里,如果在数组首部,我们就改变了最终得到的数组。|p-q|次操作我们可以操作在数组首部的次数有0,1,2……|p-q|。总共有|p-q|+1种情况。 #include<iostream>#include<vect...

小蓝有很多数字卡片，每张卡片上标有 0到9 中的一个数字。他想用这些卡片从 1 开始拼出连续的正整数，每拼一个数，就把用到的卡片保存起来，之后不能再用这些卡片拼其他数。例如，如果小蓝手里有 30 张卡片，每个数字 0到9 各 3 张，他可以拼出 1到10，但是拼 11 时，数字 1 的卡片已经不够用了。现在，小蓝手里有每个数字 0到9 的卡片各 2021 张（总共 20210 张），问他能够从 1 拼到的最大连续整数是多少？这道题的思路也很简单,咱们准备一个十个空间大小的数组vec[10],都存储2021,代表0~9的卡片都有2021张,遍历从1开始的数,我们将它逐位分解,对于分解出的每一位x,vec[x]—，直到某个数分解出的某位i,vec[i]=0时,说明没有卡片去给它组成这个数了，那么答案就是这个数的上一个数。#include<iostream>#include<vector>using namespace std;vector<int> vec(10,2021);int work(){ for(int i=1;;i++)...

k倍区间题目描述给定一个长度为 $N$ 的数列， $A_1, A_2, \cdots A_N$。如果其中一段连续的子序列 $A_i, A_{i+1}, \cdots A_j (i \le j)$ 之和是 $K$ 的倍数，我们就称这个区间 $[i, j]$ 是 K 倍区间。你能求出数列中总共有多少个 $K$ 倍区间吗？输入描述第一行包含两个整数 $N$ 和 $K$ $(1 \le N, K \le 10^5)$。以下 $N$ 行每行包含一个整数 $A_i$ $(1 \le A_i \le 10^5)$。输出描述输出一个整数，代表 K 倍区间的数目。输入输出样例示例输入 5 212345 输出 6 前缀和：计算数组的前缀和 $S$。同余定理：如果区间 $[i, j]$ 的和是 $K$ 的倍数，即 $(S_j - S_{i-1}) \% K == 0$，这意味着 $S_j \% K == S_{i-1} \% K$。转化：只需要计算前缀和模 $K$ 的余数。如果有 $c$ 个前缀和的余数相同（比如都是 1），那么从这 $c$ 个位置中任选 2 个（$C_c^2$），它们之...

问题描述小明是学校里的一名老师，他带的班级共有 $n$ 名同学，第 $i$ 名同学力量值为 $a_i$。在闲暇之余，小明决定在班级里组织一场拔河比赛。为了保证比赛双方实力尽可能相近，需要在这 $n$ 名同学中挑选出两个队伍，队伍内的同学编号连续：${a_{l_1}, a_{l_1+1}, \dots, a_{r_1}}$ 和 ${a_{l_2}, a_{l_2+1}, \dots, a_{r_2}}$，其中 $l_1 \le r_1 < l_2 \le r_2$。两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。输入格式输入共两行。第一行为一个正整数 $n$。第二行为 $n$ 个正整数 $a_i$。输出格式输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。样例输入510 9 8 12 14 样例输出1 样例说明其中一种最优选择方式：队伍 1：${a_1, a_2, a_3}$，队伍 2：${a_4, a_5}$，力量值和分别为 $10+9+8=27$，$12+14=26$，差距为 $|27-2...

向量 vector#include <vector>连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。常用方法构造vector<类型> arr(长度, [初值])#include<vector>vector<int> arr(100,0); //构造初始长为100的int一维数组,初始值全为0vector<vector<int>>arr(100,vector<int>()); //构造行数为100,列数不定的二维数组vector<vector<int>>arr(100,vector<int>(666,-1)); //构造行数为100,列数为666的二维数组,初始值为-1 尾接 & 尾删 .push_back(元素)：在 vector 尾接一个元素 .pop_back()：删除 vector 尾部的一个元素获取长度.size()获取当前 vector 的长度清空.clear()清空 vector判空.empty()如果是空返回 true 反...

评论

数据加载中