algorithm - Fenwick 树确定一个点落在哪个区间

Question

设 a₀,...,a_n-1 是一个长度序列。我们可以构造区间 [0,a₀], (a₁,a₂+a₁], (a₂+a₁,a₃+a₂+a₁ ],... 我将序列 a₁,...,a_n-1 存储在 Fenwick 树中。

我问这个问题:给定一个数字 m，我如何有效地(记录 n 次)找到 m 属于哪个区间？

例如，给定 a:3、5、2、7、9、4。

分域树存储 3、8、2、17、9、13。

区间为 [0,3],(3,8],(8,10],(10,17],(17,26],(26,30)。

给定数字 9，算法应返回分域树的第 3 个索引(如果使用基于 0 的数组则为 2，如果使用基于 1 的数组则为 3)。给定数字 26，算法应返回 Fenwick 树的第 5 个索引(如果使用基于 0 的数组则为 4，如果使用基于 1 的数组则为 5)。

可能另一种数据结构更适合此操作。我使用 Fenwick Trees 是因为它们看起来简单高效。

Answer 1

我们可以得到一个 O(log n) 时间的搜索操作。诀窍是将二分搜索与前缀求和运算结合起来。

def get_total(tree, i):
    total = 0
    while i > 0:
        total += tree[i - 1]
        i -= i & (-i)
    return total


def search(tree, total):
    j = 1
    while j < len(tree):
        j <<= 1
    j >>= 1
    i = -1
    while j > 0:
        if i + j < len(tree) and total > tree[i + j]:
            total -= tree[i + j]
            i += j
        j >>= 1
    return i + 1


tree = [3, 8, 2, 17, 9, 13]
print('Intervals')
for i in range(len(tree)):
    print(get_total(tree, i), get_total(tree, i + 1))
print('Searches')
for total in range(31):
    print(total, search(tree, total))

输出是

Intervals
0 3
3 8
8 10
10 17
17 26
26 30
Searches
0 0
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 1
9 2
10 2
11 3
12 3
13 3
14 3
15 3
16 3
17 3
18 4
19 4
20 4
21 4
22 4
23 4
24 4
25 4
26 4
27 5
28 5
29 5
30 5