我的问题是我有一个大小为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的形式）的纯功能树，因此具有固定的深度。这可能是解决您的问题的最快解决方案，无论是最差的还是现实的。
我知道的唯一其他部分持久性阵列在最坏的情况下可能需要更长的时间。如果以各种受限制的方式访问数组，则某些组件具有更好的分期复杂性，并且有些预期复杂性更好。