C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例

相关

源码测试用例下载
https://download.csdn.net/download/he_zhidan/88430716 包括4个压缩包，初始代码，实现前缀和，实现前缀积，实现前缀异或。都是在前者的基础上修改的。
本博文是CSDN学院课程的讲义
https://edu.csdn.net/course/detail/38771

前缀和（前缀积、前缀异或）应用的博文

【前缀和]LeetCode1862：向下取整数对和

C++前缀和算法:统计美丽子字符串

C++前缀和算法的应用：最大化城市的最小供电站数目

C++前缀和算法的应用：使数组相等的最小开销

C++前缀和算法的应用：预算内的最多机器人数目
C++前缀和算法的应用：统计得分小于K的子数组数目

C++前缀和算法的应用：从栈中取出 K 个硬币的最大面值和
C++前缀和算法的应用：摘水果 原理源码测试用例
C++前缀和算法的应用：装包裹的最小浪费空间

C++前缀和算法的应用：统计得分小于K的子数组数目

C++前缀和算法的应用：用地毯覆盖后的最少白色砖块

C++前缀和算法的应用：分割数组的最多方案数

C++前缀和算法的应用：石头游戏 VIII 原理源码测试用例
C++前缀和算法：生成数组原理、源码及测试用例
C++前缀和算法的应用：向下取整数对和 原理源码测试用例
C++前缀和算法的应用：得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例
C++前缀和算法的应用：从仓库到码头运输箱子原理、源码、测试用例
C++前缀和算法：合并石头的最低成本原理、源码及测试用例
C++前缀和算法的应用：DI序列的有效排列
C++前缀和算法应用：和至少为 K 的最短子数组
C++算法前缀和的应用：得分最高的最小轮调的原理、源码及测试用例
C++算法前缀和的应用：分割数组的最大值的原理、源码及测试用例
C++前缀和算法应用：矩形区域不超过 K 的最大数值和
C++前缀和算法：构造乘积矩阵

原理

长度为n的数组nums，共有n+1个以nums[0]开始的子数组。索引范围分别为[0,i)，i取值区间[0,n]。preSum[i]记录子数组[0,i)的和。比如：nums = {1,2,3,4},则preSum = {0,1,3,6,10}。通过preSum，我们可以求任意nums的子数组和。子数组[i,j)等于子数组[0,j)减去[0,i)，也就是子数组[i,j)的和等于preSum[j] – preSum[i]。如果i等于j，则preSum[i]-preSum[i]，和为0，符合计算公式。如果i大于j，则非法，需要提前排除。

暴力法

时间复杂度O(n*n)。

核心代码

class CPreSum
{
public:
//左闭右开空间
long long SumO2(int left, int r)
{
long long llRet = 0;
for (; left < r; left++)
{
llRet += m_sums[left];
}
return llRet;
}
vector m_sums;
};

测试代码

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

void Test1()
{
CPreSum preSum;
preSum.m_sums = { 1,2,3,4 };
vector ans = { 0,1,3,6,10 };
auto res = preSum.SumO2(0, 4);
Assert(10LL, res);
res = preSum.SumO2(0, 3);
Assert(6LL, res);
res = preSum.SumO2(0, 2);
Assert(3LL, res);
res = preSum.SumO2(0, 1);
Assert(1LL, res);
res = preSum.SumO2(0, 0);
Assert(0LL, res);
res = preSum.SumO2(1, 4);
Assert(9LL, res);
res = preSum.SumO2(1, 3);
Assert(5LL, res);
}

void Test2()
{
srand(time(nullptr));
int n = rand() % 10 + 1;
CPreSum preSum;
for (int i = 0; i < n; i++)
{
preSum.m_sums.emplace_back(rand() % 10000);
}
preSum.Init();
for (int left = 0; left < n; left++)
{
for (int r = left; r <= n; r++)
{
long long res1 = preSum.SumO1(left, r);
long long res2 = preSum.SumO2(left, r);
assert(res1==res2);
}
}
}
int main()
{
Test1();
Test2();
}

前缀和

时间复杂度O(n)，预处理O(n)，每次查询O(1)。

代码

void Init()
{
m_vPreSum.emplace_back(0);
for (const auto& n : m_nums)
{
m_vPreSum.emplace_back(n + m_vPreSum.back());
}
}
long long SumO1(int left, int r)
{
return m_vPreSum[r] - m_vPreSum[left];
}
vector m_vPreSum;

前缀乘积

只需要修改三处m_vPreSum[0]=1，+变成*，-变成除。

修改后的代码

class CPreSum
{
public:
//左闭右开空间
long long SumO2(int left, int r)
{
long long llRet = 1;
for (; left < r; left++)
{
llRet *= m_nums[left];
}
return llRet;
}
void Init()
{
m_vPreSum.emplace_back(1);
for (const auto& n : m_nums)
{
m_vPreSum.emplace_back(n * m_vPreSum.back());
}
}
long long SumO1(int left, int r)
{
return m_vPreSum[r] / m_vPreSum[left];
}
vector m_vPreSum;
vector m_nums;

};

前缀异或

C语言异或的符合是^{，初始0,也就是m_vPreSum.emplace_back(0)。异或的逆运算是本身，所以乘除都换成}。

其它

视频课程

要是你认为本篇难道较大，不好入手，推荐你先学习基础算法的课程，我已完成部分，余下部分持续更新中，就在CSDN学院。
https://edu.csdn.net/course/detail/38771

C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

相关下载

如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653