python - 快速访问成对操作的总和

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)在时间和空间上(最好是线性的)。

Answer 1

对于二元运算，例如 or, and, xor , O(N)算法是可能的。
让我们在这个例子中考虑 XOR，但这也可以很容易地修改为 OR/AND。
这里要注意的最重要的事情是，位 x 上的二元运算符的结果。两个数字的结果不会影响位 y 的结果. (您可以通过尝试类似 010 ^ 011 = 001 之类的方法轻松看到这一点。因此，我们首先计算所有数字的最左边位对最终总和的贡献，然后是下一个最低有效位，依此类推。这是一个简单的算法/伪代码为了那个原因:

构造一个简单的表 dp ，其中 dp[i][j] = count of numbers in range [i,n) with jth bit set

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) .