快速访问成对操作的总和

Question

给定一个数字向量v，我可以通过使用累计和来访问该向量的各个部分的总和，即使用O(n)的方式。

v = [1,2,3,4,5]
def sum_v(i,j):
    return sum(v[i:j])

我能够做到O(1)

import itertools
v = [1,2,3,4,5]
cache = [0]+list(itertools.accumulate(v))
def sum_v(i,j):
    return cache[j] - cache[i]

现在，我需要类似的东西，但是针对的是pairwise而不是sum_v:

def pairwise(i,j):
    ret = 0
    for p in range(i,j):
        for q in range(p+1,j):
            ret += f(v(p),v(q))
    return ret

其中f, 最好是, 一些相对任意的东西 (例如, * 或 ^ 或 ...). 不过，仅适用于乘积或XOR的某些东西也不错。

PS1。我寻求的是以O表示的速度提升，而不是通用的memoization，如functools.cache。

PS2。这个问题是关于算法，而不是实现，因此是与语言无关的。 我只标记了python，因为我的示例是用python编写的。

PS3。显然，可以预先计算所有的pairwise值，因此解决方案应该是时间和空间复杂度都为o(n^2)（最好是线性）。

- sds

---

我认为在这里你做不到比O(N^2)更好，因为有N^2个值需要考虑。可以进行的任何优化都与运算符的属性相关（例如：如果操作是XOR，则可以进行位操作等）。 - Abhinav Mathur

@AbhinavMathur：谢谢，如果是异或运算，你会怎么做？(f=^) - sds

NumPy 是一个选项吗？ - Pranav Hosangadi

@PranavHosangadi：我正在寻找一个算法，而不是它的实现；如果numpy实现了某些东西，我可以处理它。然而，问题在于O方面的加速，而不是重写为C。 - sds

我建议不要将问题限制在O(n)的预处理时间和空间上 - 有一些有趣的数据结构，比如线段树，它们使用O(n log n)的空间，在O(log n)的时间内进行查找，这仍然比朴素方法更好。 - kaya3

Answer 1

对于二进制运算，例如 或、与、异或，可以使用 O(N) 算法。
让我们以异或为例，但这也可以很容易地修改为或/与。
最重要的是要注意，在两个数字的位 x 上进行二进制运算的结果不会影响位 y 的结果。(你可以轻松地尝试一些像 010 ^ 011 = 001 的东西来看到这一点。因此，我们首先计算所有数字的最左边位对最终和的贡献，然后是次最低有效位，以此类推。下面是一个简单的算法/伪代码：

1. 构建一个简单的表 dp，其中 dp[i][j] = 范围 [i,n) 中具有第 j 位设置的数字数目

l = [5,3,1,7,8]
n = len(l)
ans = 0

max_binary_length = max(log2(i) for i in l)+1  #maximum number of bits we need to check

for j in range(max_binary_length):
    # we check the jth bits of all numbers here
    for i in range(0,n):
        # we need sum((l[i]^l[j]) for j in range (i+1,n))
        current = l[i]
        if jth bit of current == 0:
            # since 0^1 = 1, we need count of numbers with jth bit 1
            count = dp[i+1][j]
        else:
            # we need count of numbers with jth bit 0
            count = (n-i)-dp[i+1][j] 
            # the indexing could be slightly off, you can check that once
        ans += count * (2^j)
        # since we're checking the jth bit, it will have a value of 2^j when set
print(ans)

在大多数情况下，对于整数而言，位数 <= 32。因此，这应该具有复杂度 O(N*log2(max(A[i]))) == O(N*32) == O(N)。

- Abhinav Mathur

Answer 2

原则上，您始终可以在Θ(n²)的空间中预先计算每个可能的输出，然后通过在预计算表中查找来以Θ(1)的速度回答查询。其他所有内容都是一种权衡，取决于预计算时间、空间和实际计算时间的成本；有趣的问题是可以用o(n²)的空间做些什么，即次二次方的。这通常取决于应用程序以及二元操作f的属性。

在特定情况下，当f为*时，我们可以只使用Θ(n)的空间获得Θ(1)的查找：我们将利用p < q对的总和等于所有对的总和减去p = q对的总和，再除以2以考虑p > q对的情况。

# input data
v = [1, 2, 3, 4, 5]
n = len(v)

# precomputation
partial_sums = [0] * (n + 1)
partial_sums_squares = [0] * (n + 1)
for i, x in enumerate(v):
    partial_sums[i + 1] = partial_sums[i] + x
    partial_sums_squares[i + 1] = partial_sums_squares[i] + x * x

# query response
def pairwise(i, j):
    s = partial_sums[j] - partial_sums[i]
    s2 = partial_sums_squares[j] - partial_sums_squares[i]
    return (s * s - s2) / 2

更一般地，只要f是可交换的并且分布在累加器操作(+)上，这个方法就可以工作。我在此处提供的示例没有使用itertools，因此更容易转换为其他语言，因为这个问题是通用的。

- kaya3