整數範圍內的整數

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）對於具有分段樹知識的人來說非常合理。 –

整數範圍內的整數

回答

相關問題