芬威克树确定点落入的间隔 [英] Fenwick trees to determine which interval a point falls in

问题描述

让a ₀ ，...，a _n-1 为长度序列。我们可以构造区间[0，a ₀ ]，（a ₁ ，a ₂ + a ₁ ]， （a ₂ + a ₁ ，a ₃ + a ₂ + a ₁ ]，...我将序列a ₁ ，...，a _n-1 存储在Fenwick树中。

Let a₀,...,a_n-1 be a sequence of lengths. We can construct intervals [0,a₀], (a₁,a₂+a₁],(a₂+a₁,a₃+a₂+a₁],... I store the sequence a₁,...,a_n-1 in a Fenwick tree.

我问一个问题：给定一个数字m，我如何有效地（登录n个时间）找出m落入哪个区间？

I ask the question: given a number m, how can I efficiently (log n time) find into which interval m falls?

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

For example, given the a: 3, 5, 2, 7, 9, 4.

Fenwick Tree存储3、8、2、17、9、13。

The Fenwick Tree stores 3, 8, 2, 17, 9, 13.

间隔为[0,3]，（3,8]，（8,10]，（10,17]，（17,26]，（26,30]。

The intervals are [0,3],(3,8],(8,10],(10,17],(17,26],(26,30].

给出数字9，该算法应返回Fenwick树的第三个索引（如果使用基于0的数组，则返回2；如果使用基于1的数组，则返回3）。给定数字26，该算法应返回Fenwick树的第5个索引（如果使用基于0的数组，则返回4；如果使用基于1的数组，则返回5）。

Given the number 9, the algorithm should return the 3rd index of the Fenwick Tree (2 if 0-based arrays are used, 3 if 1-based arrays are used). Given the number 26, the algorithm should return the 5th index of the Fenwick Tree (4 if 0-based arrays are used or 5 if 1-based arrays are used).

可能其他数据结构可能更适合此操作。我使用的是Fenwick树，因为

Possibly another data structure might be more suited to this operation. I am using Fenwick Trees because of their seeming simplicity and efficiency.

推荐答案

我们可以获得O（log n）时间的搜索操作。诀窍是将二进制搜索与前缀和运算相集成。

We can get an O(log n)-time search operation. The trick is to integrate the binary search with the prefix sum operation.

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

这篇关于芬威克树确定点落入的间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！