给定一个整数列表。
我想知道是否可以在每个查询的 O(1) 和前提的 O(n) 的段上计算按位或？（一些前缀和）（对于每个查询的 O(log n) 和前提的 O(n log n) 很容易做到这一点，例如，使用段树，但什么更快？）
问问题
88 次
1 回答
1
对的，这是可能的。只需为每个位位置构建一个类似前缀和的数组，并用从数据开头设置的运行总位填充它。每个计数器的初始值将为零：counter[0][b]=0，并且第n- 个计数器将存储在数据项 0 到 n-1 中设置的多个位。
然后，您可以 通过测试范围两端的 -th 计数器是否不同 ( ) 来测试是否b在给定范围内的任何位置设置了位 no 。[m,n]bcounter[n+1][b] not.eq. counter[m][b]
最后从所有 (8, 16, 32...) 位位置的结果中一点一点地组成一个答案。
请注意，此解决方案要求原始数据的每一位都需要一个额外的整数，这意味着如果您的 int 为 32 位宽，则您需要例如 32 倍以上的内存。
于 2020-09-03T07:11:43.540 回答