段树上的Josephus

Question

我想用分段树来解决Joseph Flavius问题。我几乎可以肯定这个简单的模拟(即线性列表)是O(n^2)的。我想要实现的是在数组上跳跃特定的距离，取自段树。换句话说，片段树将保留有关已删除元素数量的信息，并且从树中提取一些信息将允许在O(1)中找到下一个要删除的元素。问题是我不知道如何在段树中存储信息，以使其适用于Joseph Flavius问题。

在每个节点中保留了某种额外值？但是如何查询下一个元素呢？

Answer 1

我的第一个想法是二进制搜索+给出O(log^2(n))的和的分割树。

从L到R的跳转具有以下属性：

R-L+1- sum(L，R) == skip_value

您可以使用bin-search轻松地找到具有此属性的R。当你画一个完整的圆圈时，事情会变得有点复杂，但我相信你会明白这一点。

如果有什么不清楚的地方，请随时询问。

(我也会考虑log(n)解决方案)