algorithm - 计算连续糖果的数量

Question

我正在尝试解决定义如下的问题:

A candy is represented by a number from 1 to 1e6. A person is said to have a set of k candies if he has candy 1 to k.

E.g. If a person bought candies 1, 2 and 6, then he has a set of 2 candies

Given 2 types of operations: Eat x and Buy x where x represents the candy number. Buy x will increase the quantity of x by 1 only. Eat x will decrease the quantity of x by 1 only.

For each operation, answer the question, what is the size of the set of candies that I have now?

我正试图找到最有效的方法来做到这一点。我想到的解决方案如下:

让 count[i] 定义大小为 1 - N 的数组，其中 N 是可能的最大糖果数。 count[i] 存储我目前拥有的编号为 i 的糖果的数量。

设大小为 1 - N 的 Fenwick[i] 数组，其中 N 是可能的最大糖果数。这个数组用于构建一个 fenwick 树来存储我的集合中糖果的累计总和。此累加和不使用计数数组。累计总和计算 1 的数量(每个 1 表示我的收藏中有糖果 x)。例如如果我有一组5颗糖果，那么1到5的累计和是5。如果有一组10颗糖果，那么1到10的累计和是10...

对于购买操作，如果糖果 x 不在我的收藏中，则将 1 加到从索引 x 开始的累积总和(这由 fenwick 树处理)。否则，我将只执行 count[x]++

对于吃操作，执行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 的最后一个值，其中 query(x) 给出了一个有效的集合。

解的复杂度:O(log^2(N))

Answer 1

这通常是一个二叉树结构。

为简单起见，假设糖果的索引范围是从 0 到 2^k - 1 的某个整数 k。然后每时每刻，状态都由 16 数字表示，c[0] 到 c[2^k - 1]，其中 c[i] 是糖果 i 的数量。

我们构造一个二叉树如下:根节点P(0, 2^k)代表整个区间[0, 2^k)；对于满足b - a > 1的每个节点P(a, b)，构建两个子节点P(a, (a + b)/2) 和 P((a + b)/2, b)。

令 p(a, b) 为 i 在 [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 的情况，因此有 c[0] 到 c[7]。例如:

c[0 .. 7] = {1, 3, 0, 4, 3, 2, 8, 1}

树形结构如下所示:

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

现在假设我们将1加到c[2]上，变成1，那么我们只需要更新数字 p(2, 3), p(2, 4), p(0, 4), p(0, 8)。