所以我有一个数组'a0'的大小，比如说105，现在我必须在这个数组中做一些更改可以使用函数f（ai-1）计算第i个变化，以O（1）时间给出ai，其中aj表示对其进行第j个变化后的数组“a”也就是说，如果我们在恒定时间内知道ai-1，就可以计算出ai。我知道我必须事先做105次修改。
现在这个问题要求我回答大量的查询，比如ai[p]-aj[q]，其中ax[y]表示对数组a0进行第x次更改后数组的yth元素。
现在如果我有1010阶的空间，我可以通过预先存储所有105个数组在o（1）中轻松地解决这个问题，但我（通常）没有这样的空间。我也可以在每次从头开始生成AI和AJ并回答查询时回答这些问题，但是我也负担不起这样的时间复杂度，所以我想知道我是否可以使用一些数据结构来监控这个问题。
编辑：示例：
我们定义了一个数组b={1,3,1,4,2,2,6}，定义了aj，定义aj，aj是在b中添加第j个元素后存储第i个数字频率的数组，即a0={0,0,0,0,0,0,0,0,0}现在a1={1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}，a3={2,0,0,0,1,0,1，1,0,0}和a6={2,1,1,1,0,1}。
f（aj）只需向b添加一个元素并更新aj-1的值。
最佳答案
如果存在一些最大的状态N，那么检查点是一个很好的去路。例如，如果N=100,000，您可能有：
c0 = [3, 5, 7, 1, ...]
c100 = [1, 4, 9, 8, ...]
c200 = [9, 7, 1, 2, ...]
...
c10000 = [1, 1, 4, 6, ...]
现在你有1000个检查站您可以在o（1）时间内找到最接近任意状态
x的检查点，最多可以在99次操作中重建x。把我对你的问题和John Zwinck's answer的评论抄下来，如果你的变异函数
f(*)很昂贵，而且它的影响仅限于少数元素，那么你可以存储增量的变化。这样做不会降低算法的时间复杂度，但可以减少运行时间。如果你有无限的空间，你只需要存储所有的检查点既然没有，就必须适当地平衡检查点的数量和增量。这将需要一些实验，可能集中在确定
f(*)的成本和其影响的程度。另一个选择是查看查询行为。如果用户倾向于重复查询相同或附近的位置，则可以利用LRU (least-recently used) cache。