整数范围内的整数

A是一个包含至多10个整数的数组。整数范围内的整数

我们必须在log（N）复杂度（其中，N = A中的元素数）对此阵列执行2种操作。

操作1，给定v，我，Ĵ我们必须v添加到A [k]的（ⅰ< = K < = j）的。

操作2，给出我 & Ĵ计算（A [I] * A [I + 1] * A第[i + 2] * ... * A [j]）％M 。（M是素数，对于所有操作都是一样的）。

将会有大约10 作业。

如果log（N）不可能，那么做这些操作的最佳复杂度是多少？

2013-08-21 Bidhan Roy

对于操作1，你真的是指'添加v'还是'乘以v'？对于'乘以v'，我的解决方案可以更容易地适应。我仍然认为细分树是'O（log N）'解决方案的可行选择，但目前我看不到操作1。你用spoj标记了这个，你能链接到spoj问题吗？ – IVlad

@IVlad我也想出了**乘以v **可以通过分段树或二叉索引树来完成。这不是一个特定的spoj问题，但知道这个技巧将帮助我解决spoj的几个问题。 –

试图解决这个问题;我也相信次线是可能的。我还没有完全解决这些问题，但我敢打赌，它将涉及这样的事实（从'0'到'M-1'的整数，加模M'，乘模M' ）形成一个领域。 –

因为它看起来像你要访问的所有元素的范围[i, j]，复杂性取决于范围的线性尺寸，

来源

2013-08-21 14:29:11

那么，第一个操作可以通过使用一些数据结构以log（K）复杂度完成，其中K是该范围的线性大小。使用数据结构技术可能也是第二个也可以用相同的复杂性来完成的。 –

然后找到一种方法来做到这一点，而不必访问所有的元素。：P –

@DennisMeng - 虽然我一定会努力做到这一点，但我无法做到这一点并不能证明这是不可能的。 – IVlad

这有可能是吉是N的数量级上。而你必须改变他们每个人。这使得任何算法都比O（N）更快，Paul说。 K不是问题的参数，它只是一个变量，因此Bidhan的答案中的log（K）是没有意义的。现在，如果问题不是关于时间复杂度的问题，而是关于大规模并行操作树的高度（比如你在CUDA上），那么给定足够的线程可以平均执行操作由于所有操作的独立性，O（1）中的1和O（log（N））中的操作2通过乘以mod M对相邻元素（需要100000/2个线程），然后是相邻结果对等，直到答案已达到。

然而，这不是问题。除了大规模并行计算外，每个操作的复杂性都是O（N），无论你如何执行该操作。

来源

2013-08-21 15:05:59 Michael

“你必须改变他们每个人”并不遵循。即使比“O（N）”更快（我非常怀疑），这不是一个证明。您不一定必须更改它们中的每一个，存储关于它们已被更改并仍能够回答操作2查询的事实的信息可能已足够。 – IVlad

是的，正如** IVIad **所说，你不需要访问每个元素来计算答案。而且，日志（K）对于具有分段树知识的人来说非常合理。 –

整数范围内的整数

回答

相关问题