我试图解决一个定义如下的问题：
糖果由1到1e6的数字表示一个人
据说他有一套K糖果，如果他有1到K的糖果。
例如，如果一个人买了糖果1、2和6，那么他有一套2
糖果
给定两种操作：Eat x和Buy x，其中x表示
糖果号码买x只会使x的数量增加1吃x
只会使x的数量减少1。
每次手术，回答问题，我现在的糖果有多大？
我正试图找到最有效的方法来做这件事。我想到的解决办法如下：
让count[i]定义大小为1-n的数组，其中n是最大可能的糖果数。count[i]存储我目前拥有的糖果数量。
让fenwick[i]数组的大小为1-n，其中n是最大可能的糖果数。这个数组用于构建一个fenwick树来存储我的收藏中累积的糖果总量。此累积和不使用计数数组累积总和计算1的数量（每个1表示我的收藏中存在一个糖果x）。如果我有一套5个糖果，那么从1到5的累计总和是5。如果有一套10个糖果，那么从1到10的累计总和是10…
对于购买操作，如果candy x不在我的集合中，则从索引x开始向累积和添加1（这由fenwick树处理）否则，我就执行count[x]++
对于eat操作，执行count[x]--如果count[x]现在是0，那么我从索引x开始的累积和中减去1（这是由fenwick树处理的）。
现在解决了插入和删除的部分。最困难的是如何得到目前收藏的糖果的尺寸。
我试图在fenwick树中查询最大的索引i，对于这个索引，从1到i的累计和等于i，同时每次都以2的幂递增查询索引。
我取一个最大的索引，它是一组有效的糖果j，最小的索引是一组无效的糖果k。然后从j循环到k，在每次迭代中查询fenwick树。循环命中无效集合后，中断并输出答案。
在我看来这是可行的。然而，这肯定不是一个有效的方法。有人能告诉我更好的解决办法吗？提前谢谢。
编辑（解决方案）：
我的插入和删除方法是正确的。只是我在寻找一个不正确的方式收集糖果在这种情况下，我们需要最大的数字x，其中query（x）=x（query（x）给出从1到x的累积和）所以我们可以使用二进制搜索来找到x（query（x）=x）的最大有效值。为了实现这一点，我们只需要保留一个额外的变量来跟踪查询（x）给出有效集合的最后一个x值。
解的复杂性：O（log ^ 2（n））
最佳答案
这通常是一个二叉树结构。
为了简单起见，让我们假设糖果的指数从0到2^k - 1不等，对于一些整数k。然后在每个时刻，状态都由16个数表示，c[0]到c[2^k - 1]，其中c[i]是糖果的数量。
我们构造了一个二叉树：根节点代表整个区间，对于每个节点，构造两个子节点。
设i为P(0, 2^k)的最小值。显然我们有：[0, 2^k)；P(a, b)如果b - a > 1。
构建了这个数据结构之后，对于每个操作（加1或减1），我们可以从下到上以P(a, (a + b)/2)步骤更新数据。此外，还可以通过P((a + b)/2, b)步骤来确定糖果的尺寸。
数据结构示例：
让我们看看这个案例，这样就有了p(a, b)到c[i]。例如：i
树结构如下所示：
p(0, 8) = 0
|- p(0, 4) = 0
| |- p(0, 2) = 1
| | |- p(0, 1) = 1
| | |_ p(1, 2) = 3
| |_ p(2, 4) = 0
| |- p(2, 3) = 0
| |_ p(3, 4) = 4
|_ p(4, 8) = 1
|- p(4, 6) = 2
| |- p(4, 5) = 3
| |_ p(5, 6) = 2
|_ p(6, 8) = 1
|- p(6, 7) = 8
|_ p(7, 8) = 1
现在假设我们将
[a, b)添加到数字p(a, a + 1) = c[a]，这就是p(a, b) = min{p(a, (a + b)/2), p((a + b)/2, b)}，那么我们只需要更新数字b - a > 1，O(k)，O(k)，k = 3。