arrays - 增加时间复杂度以克服空间复杂度

Question

所以我有一个大小为 10⁵ 的数组“a₀”，现在我必须对该数组进行一些更改。可以使用函数 f(a_i-1) 计算第 i 个变化，在 O(1) 时间内给出 a_i，其中 a_j 表示第 j 次更改后的数组“a”。这意味着如果我们在常数时间内知道 a_i-1 就可以计算出 a_i 。我知道我必须事先进行 10⁵ 更改。

现在问题要求我回答大量查询，例如 a_i[p]-a_j[q]，其中 a_x[y]，表示对数组 a₀ 进行第 x 次更改后数组的第 y 个元素。

现在如果我有 10¹⁰ 数量级的空间，我可以通过预先存储所有 10⁵ 数组在 O(1) 中轻松解决这个问题，但是我(通常)没有那种空间。我也可以通过每次从头开始生成 a_i 和 a_j 并回答查询来回答这些查询，但我也无法承受那种时间复杂性，所以我想知道我是否可以使用某种数据结构来监控这个问题。

编辑:示例:

我们定义一个数组B={1,3,1,4,2,6}，我们定义a_j为存储第j个元素加入后第i个数出现频率的数组到 B。也就是说，a₀={0,0,0,0,0,0} 现在 a₁={1,0,0,0,0 ,0}, a₂={1,0,1,0,0,0}, a₃={2,0,1,0,0,0 } a₄={2,0,1,1,0,0} a₅={2,1,1,1,0,0} 和 a< sub>6={2,1,1,1,0,1}.

f(a_j) 只是将 a 元素添加到 B 并更新 a_j-1 的值。

Answer 1

假设每次迭代更改的元素数远小于元素总数。存储一个列表数组，其中列表元素为(i, new_value)。例如，如果完整 View 是这样的:

a0 = [3, 5, 1, 9]
a1 = [3, 5, 1, 8]
a2 = [1, 5, 1, 0]

我们将存储这个:

c0 = [(0, 3), (2, 1)]
c1 = [(0, 5)]
c2 = [(0, 1)]
c3 = [(0, 9), (1, 8), (2, 0)]

然后对于查询a2[0] - a1[3]，我们只需要查询c0和c3(查询)。我们可以使用二进制搜索来定位必要的索引 2 和 1(二进制搜索的键是元组的第一个元素)。

两次二分搜索的查询时间为 O(log N)，其中 N 是数组中单个值的最大更改次数。空间是O(L + M)，其中L是原始数组的长度，M是所做更改的总数。