ddl 7.26
熟悉你的框架
对于一个基本数据结构，我们一定会涉及以下四个部分：增、删、查、改，对于 B+ 树也不例外。为了减少大家的工作量，我们引入了一套非常优秀的框架，框架已经正确地实现了这些基本功能。不过，在增加新功能之前，我们希望你们尽可能熟悉这套框架的内容，包括但不限于接口的使用等。因此，第一个部分主要需要完成 main 函数中的测试，并利用 point query 实现最简单的 range query。
具体来说，框架的作者提出了一些测试数据，你们需要实现 main.cpp 文件，读取测试数据，调用相关接口完成计算，然后按照规定输出结果。另外，查询操作分为两大类：点查询（point query）与范围查询（range query），一种最简单的 range query 的实现即为很多个 point query，在这个部分可以使用这种 brute force 的策略实现 range query。
具体来说，你需要在 main.cpp 中通过以下测例：
第一行为四个整数 n m p q
后面 n 行每行为一个 kv 对，保证 key 不重复，需要插入 map 中
接下来有 m 个点查询，每行给定一个 key，若存在则输出对应的 value，否则输出 NOT FOUND
然后 p 行每行为一个 kv 对，需要在 map 中更新，保证每个 key 都曾被插入过
接下来有 q 个范围查询，每行给定 lvalue 与 rvalue，请输出在 [lvalue, rvalue) 中出现的 key 的个数
输入保证所有数据均为 int 类型，保证区间合法也即 lvalue < rvalue
测试样例在 testcase/0 目录下，时间限制为 60s，从标准输入读取，并输出到标准输出
n = 1e6
m = 1e4
p = 2e5
q = 1e1
ddl 8.1
更加高效的范围查询
在 Part II 中我们熟悉了 B+ 树的代码框架与基本接口使用，并用非常原始的方式实现了范围查询。这很简单，但也确实非常低效。如果在中间节点存储相关信息，是否可以避免很多深入遍历的过程？请思考如何在结点上维护额外的信息，从而大幅增加 range query 的效率。注意你可能需要仔细观察框架中增删改的操作，结点中的额外信息在很多部分都要额外维护。我们会从正确性、性能和设计思路的方面进行评价。
请改进你的程序，使之通过以下测例：
第一行有一个整数 n
接下来有 n 行操作，格式为 op i j
若 op=i 表示插入操作，此时 i j 分别为 key value，插入树中
若 op=r 表示范围查询，此时 i j 分别为 lvalue 与 rvalue，含义与 Part I 中一致
你可以选择继续使用 btree_map，也可以不存储 value，换而使用 btree_set，性能应该不会有显著差异
为了避免输入速度影响程序性能，推荐使用一些快速读入，一份可用的模版如下
inline int read() {
char c = getchar();
int x = 0, s = 1;
while (c < '0' || c > '9') {
if (c == '-')
s = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * s;
}题目保证输入合法，数据类型均为 int，从标准输入读取，并输出到标准输出
评分标准待更新，约 8pts 为性能分，将对后十个公开测试样例耗时取平均，通过曲线保序映射在 100% 到 60% 之间；样例约 1/4 白给，1/2 考察是否通过在中间结点维护额外信息，从而避免大量叶子结点访问，1/4 为 corner cases；可能会有白盒分，但只有代码规范非常糟糕时才会扣分（变量非常奇怪的起名如 aaa bbb 等、代码缩进乱到影响正常阅读等）
注意样例中并没有涉及结点的删除，因此框架中 remove 操作可以不进行修改，不过仍然建议有兴趣的同学进行尝试；请不要钻空子，，如使用二分查找而不是 B+ 树完成实验，或仅把框架当成一个快速的 map API 使用。如果你觉得模棱两可，可以私聊助教。