我的問題是我有一個大小爲N的對象數組。在每次（t + 1）之後，數組中的某些值可能會更改，也可能不會更改。所以讓我們說t + 1指數15變化，但其他一切保持不變。什麼是最有效的數據結構來存儲部分改變數組的時間序列？
除了僅僅擁有一個數組數組之外，什麼是最有效的方法來存儲這樣的內存呢？我希望能夠隨時獲得數組的所有值，以最有效的方式說getValues（很長一段時間）。
說4個陣列
時間1個 空 空 空 XYZ
時間2 空 空 ABC XYZ
（注意，只有農行在這裏改變了），但我們仍然保持時間1的最後一個索引的值。
你所要求的在學術CS領域被稱爲「部分持久陣列」。有關持久性的更多信息，請參閱the survey of Kaplan。
一個簡單的解決方案是使用搜索樹而不是數組。您可以使用純功能均衡搜索樹來保證每次讀取或寫入都需要O（lg n）最差情況時間（其中n是數組大小），而不是O（1）時間。 （如果將時間戳版本保留在可擴展陣列中，則添加新版本爲O（1）分期付款，訪問舊版本爲O（1）最差情況。）
如果您對純粹不熟悉功能搜索樹，你可能會讀this introduction to Clojure's persistent arrays。它們是固定寬度的整數（以trie的形式）的純功能樹，因此具有固定的深度。這可能是解決您的問題的最快解決方案，無論是最差的還是現實的。
我知道的唯一其他部分持久性陣列在最壞的情況下可能需要更長的時間。如果以各種受限制的方式訪問數組，則某些組件具有更好的分期複雜性，並且有些預期複雜性更好。