快速访问成对运算的和

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。我希望在^{}方面有一个加速，而不是像^{}这样的泛型memoization

PS2。问题在于算法，而不是实现，因此语言不可知。我之所以给它加上标签python，只是因为我的示例是用python编写的

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

Answer 1

原则上，您总是可以在Θ（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的例子，因此它更容易翻译成其他语言，因为这个问题是不可知语言的

Answer 2

对于诸如or, and, xor之类的二进制操作，可以使用O(N)算法。
让我们考虑这个例子的XOR，但这可以很容易地修改为//和。 这里需要注意的最重要的一点是，两个数字的位x上的二进制运算符的结果不会影响位y的结果。（您可以通过尝试类似010 ^ 011 = 001的方法很容易看出这一点。因此，我们首先计算所有数字中最左边的位对最终和的贡献，然后是下一个最低有效位，依此类推。下面是一个简单的算法/伪代码：

1. 构造一个简单的表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)的复杂性