【C++二分查找 树状数组】2424. 最长上传前缀

本文涉及的基础知识点

C++二分查找
树状数组

LeetCode2424. 最长上传前缀

给你一个 n 个视频的上传序列，每个视频编号为 1 到 n 之间的 不同 数字，你需要依次将这些视频上传到服务器。请你实现一个数据结构，在上传的过程中计算 最长上传前缀 。
如果 闭区间 1 到 i 之间的视频全部都已经被上传到服务器，那么我们称 i 是上传前缀。最长上传前缀指的是符合定义的 i 中的 最大值 。
请你实现 LUPrefix 类：
LUPrefix(int n) 初始化一个 n 个视频的流对象。
void upload(int video) 上传 video 到服务器。
int longest() 返回上述定义的 最长上传前缀 的长度。
示例 1：
输入：
[“LUPrefix”, “upload”, “longest”, “upload”, “longest”, “upload”, “longest”]
[[4], [3], [], [1], [], [2], []]
输出：
[null, null, 0, null, 1, null, 3]
解释：
LUPrefix server = new LUPrefix(4); // 初始化 4个视频的上传流
server.upload(3); // 上传视频 3 。
server.longest(); // 由于视频 1 还没有被上传，最长上传前缀是 0 。
server.upload(1); // 上传视频 1 。
server.longest(); // 前缀 [1] 是最长上传前缀，所以我们返回 1 。
server.upload(2); // 上传视频 2 。
server.longest(); // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。
提示：
1 <= n <= 10⁵
1 <= video <= 10⁵
video 中所有值 互不相同 。
upload 和 longest 总调用 次数至多不超过 2 * 10⁵ 次。
至少会调用 longest 一次。

二分查找

我封装的树状数组的下标是从0开始的，故将video–。
二分类型：寻找尾端
Check函数的参数返回：[0,n]，一定有解。
Check 函数的实现：
$$\{\begin{array}{ll}直接返回true。& 0==mid\\ treeArr.Sum(mid-1)==mid& \end{array}$$

代码

核心代码

template<class ELE = int >
class CTreeArr
{
public:CTreeArr(int iSize) :m_vData(iSize + 1){}void Add(int index, ELE value){index++;while (index < m_vData.size()){m_vData[index] += value;index += index & (-index);}}ELE Sum(int index)//[0...index]之和{index++;ELE ret = 0;while (index){ret += m_vData[index];index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2);	}ELE Get(int index){return Sum(index) - Sum(index - 1);}
private:vector<ELE> m_vData;
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class LUPrefix {public:LUPrefix(int n):m_treeArr(n), m_n(n){}void upload(int video) {m_treeArr.Add(video - 1, 1);}int longest() {auto Check = [&](int mid) {if (0 == mid) { return true; }return m_treeArr.Sum(mid - 1) == mid;};return CBinarySearch<int>(0, m_n).FindEnd(Check);}CTreeArr<int> m_treeArr;int m_n;};

单元测试

	TEST_METHOD(TestMethod11){LUPrefix server(4);   // 初始化 4个视频的上传流server.upload(3);                    // 上传视频 3 。AssertEx(0, server.longest());                    // 由于视频 1 还没有被上传，最长上传前缀是 0 。server.upload(1);                    // 上传视频 1 。AssertEx(1, server.longest());                    // 前缀 [1] 是最长上传前缀，所以我们返回 1 。server.upload(2);                    // 上传视频 2 。AssertEx(3, server.longest());                     // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。