3

我遇到过一些此类问题。假设我们有一个元素数组A，其中大约是百万。我们得到了 form 的查询。在每个查询中，我们必须对元素执行一些操作。nn1'p q'A[p]A[q]

  • 这个操作是一些普通的操作之类XOR的。用于对 A（从索引 p 到 q）中的每个数字与给定数字 m 进行异或运算。对于前-A[p]^m,A[p+1]^m..A[q]^m

如果我们有数千个类型为“p q”的查询，那么我们会对重叠范围进行重复计算（例如 - p1<p2<q1<q2）。如果有空间/时间的权衡，我宁愿更快地完成我的工作，即使它需要更多的空间。所以，我专注于时间而不是空间。

我的问题是 -是否有任何数据结构可以有效地处理这些类型的查询（具有一些在进一步查询中重复的范围）。我能想到的就是做一些预处理并将东西保存在数据结构中。然后在我们收到进一步的查询时进行更新和处理。

有人可以建议一些有助于处理与某些范围有关的查询的数据结构（特别是当范围进一步广泛重复时）？

4

2 回答 2

1

我想到的第一件事是具有延迟传播的段树，但它仅在您描述的查询确实是对表的更新并且不返回结果时才真正适用。因此，会有一个 update[pq] 操作和一个 query[pq]。第一个只是使用您描述的操作进行更新，第二个返回范围中的值。

也看到这个。

于 2012-10-07T13:58:35.827 回答
0

对于 0 到 log(n) 范围内的每个 k，存储一个长度为 n/2**k 的数组 A[k]。

A[k][i] 的内容将表示数组中从索引 i*2**k 到 (i+1) 2 *k-1 的元素。

当你想对一个范围进行操作时，你将范围分成可能的最大块并更新 A[k] 中的相应条目。

例如，如果您的范围为 16->33，您将只更新 A[4][1]（表示 16->31）和 A[1][16]（表示 32->33）

当您想要访问元素中的组合值时，您需要组合每个 log(n) 数组中的操作。

例如，要访问 5，您需要组合 A[0][5] 和 A[1][2] 和 A[2][1] 和 A[3][0] 等中的操作。

这应该为范围内的每个操作以及元素的每次访问提供 O(log(n)) 成本。

于 2012-10-06T21:04:28.360 回答