使用 Fenwick Tree 对数字进行排序（借助 ChatGPT）
0/5 (0投票)
本文是在与 ChatGPT (chat.openai.com) 进行了一次新对话后撰写的。这次对话是编写一个可以将数字排序到 o(n) 的新算法的下一步。ChatGPT 表示，可以计算出一个具有 o(n) 复杂度的排序算法。
引言
几年前，我已经写了两篇关于排序数字的文章。我最近的一篇文章解释了如何使用所有元素的总和来对它们进行排序，方法是找到列表中第 n 个位置的元素编号，然后重新排列列表。
背景
您可以在 这里 阅读我之前的文章。
与 ChatGPT 的讨论
首先，今天早些时候我问 ChatGPT，是否可以通过构建一棵树来存储树中的最小值和最大值，并通过每次迭代列表来增长树来对数字进行排序。
但是，我也问了他（谁？）什么是在线算法，他给出了完整的解释。
然后，他回答说，用于排序算法的树可以是 **Fenwick 树**。
所以，我打算阅读关于 Fenwick 树的文档，但我什么也没看懂。
第一个代码作为练习
接下来，我开始编写一个 Fenwick 树的示例代码，如下所示。
[<<[
t = [ 1,2,3,4 ],
fun g(r) {
output(r & (r+1))
},
fun sum[t](r) {
res = 0,
while(r >= 0) {
res = res + t(r),
r = g(r) - 1
},
output(res)
},
fun increase[t,g](i, delta) {
foreach(j from g) {
if (j <= i) {
t(j) = t(j) + delta
}
}
},
// print(sum(1)),
// print(sum(3)),
print(g(0)),
print(g(1)),
print(g(2)),
print(g(3)),
increase(3,5),
print(list@ToSequence(t,","))
]>>]
得到的输出是错误的，并且由于对 'i' 的最低有效位计算不正确而无法工作。
我与 ChatGPT 的第二次对话
我的想法是再次请 ChatGPT 帮助我理解 Fenwick 树是如何工作的。
他的解释对我来说不清楚，我问了他（谁？）很多问题，他都能帮助我（就像一位反复讲课的老师一样）。
于是，我问了这个问题：
引用好的，那么您确定 Fenwick 树是从零到 r 求和一个范围吗？还是它抹去了之前记录的项而不是覆盖它？我很难想象 Fenwick 树的数据结构。
ChatGPT 回答我说：
引用是的，我确定 Fenwick 树可以用来高效地计算从零到
r的范围的前缀和。换句话说，它可以用来计算数组中从第一个元素到索引r处的元素的总和。Fenwick 树是一种使用二叉树构建的数据结构。树中的每个节点存储数组中某个范围的元素总和。根节点存储整个数组的总和，而叶节点存储单个元素的总和。中间节点存储其子节点范围的总和。
为了计算从零到
r的范围的前缀和，query_fenwick_tree函数会沿着一条由r的最低有效位决定的路径遍历树。它将遍历到的节点的值相加，以计算范围内元素的总和。需要注意的是，Fenwick 树不存储数组的单个元素。相反，它存储元素范围的总和。这使得它能够在不存储单个元素的情况下高效地计算范围的前缀和。
我希望这能帮助您理清思路。如果您有任何其他问题，请随时告诉我。
因此，虽然我还没有弄清楚它是如何工作的，但我开始让 ChatGPT 向我展示一种简单计算最低有效位的方法。他给了我这段代码：
def get_lsb(n):
lsb = 0
while (n & 1) == 0:
lsb += 1
n >>= 1
return lsb
# Example usage
print(get_lsb(0)) # Outputs: 0
print(get_lsb(1)) # Outputs: 0
print(get_lsb(2)) # Outputs: 1
print(get_lsb(3)) # Outputs: 0
print(get_lsb(4)) # Outputs: 2
print(get_lsb(5)) # Outputs: 0
print(get_lsb(6)) # Outputs: 1
print(get_lsb(7)) # Outputs: 0
现在，我可以编写代码并理解 **Fenwick 树算法**了。
[<<[
tree = [],
fun lsb(n) {
res = 0,
while(n > 0 && n % 2 == 0) {
res = res + 1,
n = (n - n % 2) / 2
},
output(res)
},
fun init_fenwick_tree[tree](n) {
while(n > 0) {
tree = tree 0,
n = n - 1
}
},
fun create_fenwick_tree[tree](arr) {
init_fenwick_tree(arr.length),
foreach(i from arr) {
update_fenwick_tree(i, arr(i))
}
},
fun update_fenwick_tree[tree](i, diff) {
while(i < tree.length) {
tree(i) = tree(i) + diff,
l = lsb(i),
if (l == 0)
{ i = i + 1 }
else
i = i + l,
}
},
create_fenwick_tree([1,2,3,4]),
print(list@ToSequence(tree,";"))
]>>]
现在，输出是：
1;3;6;10
1) 1
2) 3 = 1+2
3) 6 = 1+2+3
4) 10 = 1+2+3+4
之后我再次联系 ChatGPT
我问 ChatGPT：
引用是否可以使用 Fenwick 树来计算列表中所有元素的总和，然后计算每个元素的第 n 个位置来以 o(n) 的时间复杂度进行排序和重新排序？
他回答我说：
引用是的，可以使用 Fenwick 树高效地计算元素列表的前缀和，并利用这些前缀和以线性时间对元素进行排序。
以下是如何做到这一点的示例：
def sort_using_fenwick_tree(arr): # Create a Fenwick tree for the array tree = [0] * (len(arr) + 1) for i, a in enumerate(arr): update_fenwick_tree(tree, i, a) # Sort the array using the prefix sums computed by the Fenwick tree sorted_arr = [0] * len(arr) for i in range(len(arr) - 1, -1, -1): prefix_sum = query_fenwick_tree(tree, i) sorted_arr[prefix_sum - 1] = arr[i] update_fenwick_tree(tree, i, -arr[i]) return sorted_arr # Example usage arr = [5, 2, 3, 1, 4] sorted_arr = sort_using_fenwick_tree(arr) print(sorted_arr) # Outputs: [1, 2, 3, 4, 5]
排序数字的代码
修复错误
但是，之前的代码对于排序数字来说并不完善。事实上，LSB 函数的编写方式不正确。
计算 LSB 的正确方法以及此指令的工作原理
i & -i
是从一个数字开始计算其字符串表示，将最低位的 1 替换为 0，然后从该字符串（即没有最低位 1 的数字）重新计算数字，并用该结果减去输入数字。
下面的代码解释了这一点：
[<<[
fun lsb(n) {
res = [],
k = n,
while(n > 0) {
p = n % 2,
res = res p,
n = (n - n % 2) / 2
},
select {
default {
foreach(i from res) {
if (res(i) == 1) {
res(i) = 0,
jump "break"
}
}
},
break {}
},
z = 0,
i = res.length - 1,
while(i >= 0) {
z = 2 * z,
z = z + res(i),
i = i - 1
},
output(k-z)
},
count = 0,
while(count < 20) {
print("count = " count "; lsb = " lsb(count)),
count = count + 1
}
]>>]
输出现在是：
count = 0;lsb = 0
count = 1;lsb = 1
count = 2;lsb = 2
count = 3;lsb = 1
count = 4;lsb = 4
count = 5;lsb = 1
count = 6;lsb = 2
count = 7;lsb = 1
count = 8;lsb = 8
count = 9;lsb = 1
count = 10;lsb = 2
count = 11;lsb = 1
count = 12;lsb = 4
count = 13;lsb = 1
count = 14;lsb = 2
count = 15;lsb = 1
count = 16;lsb = 16
count = 17;lsb = 1
count = 18;lsb = 2
count = 19;lsb = 1
这些是 i & -i 的确切值，您可以在此 页面 上查看这些结果。
现在，我们可以构建 **Fenwick 树**了。
[<<[
fun init_fenwick_tree[tree](n) {
while(n > 0) {
tree = tree 0,
n = n - 1
}
},
fun create_fenwick_tree[tree](arr) {
init_fenwick_tree(arr.length),
foreach(i from arr) {
update_fenwick_tree(i, arr(i))
}
},
fun update_fenwick_tree[tree](i, diff) {
select {
default {
while(i < tree.length) {
tree(i) = tree(i) + diff,
l = lsb(i),
if (l == 0)
{ jump "break" }
else
i = i + l
}
},
break {}
}
},
fun query_fenwick_tree[tree](start, end) {
sum = 0,
i = end,
select {
default {
while(i >= start) {
sum = sum + tree(i),
l = lsb(i),
if (l == 0)
{ jump "break" }
else
i = i - l
}
},
break {}
},
output(sum)
},
create_fenwick_tree([1,2,6,4,2,6,7,-3,9,1,4,6,-3,1,2,5]),
foreach(i from tree) {
print(query_fenwick_tree(0,i))
}
]>>]
Fenwick 树并不是所有总和的列表。它是一个不完整的特定列表。读取树并不准确。
要计算范围内的总和，您需要调用 query_fenwick_tree(start, end)。
所以，最终的输出是：
1
3
9
13
15
21
28
25
34
35
39
45
42
43
45
50
排序算法
我不知道为什么，但 ChatGPT 给我的代码不起作用，它看起来像计数排序，但我不太确定。
于是，我写了另一个代码来进行计数排序。但最终这个代码的复杂度是 o(n^2)。
[<<[
croisements = {},
fun getIndex(sum, x) {
output(1/((sum-x)/x+1))
},
fun toInt(x) {
n = 0,
fun selectIndice(t) {
p = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
select {
break {},
default {
count = 9,
while(count >= 0) {
if (p(count) <= t) {
t = p(count),
jump "break"
},
count = count - 1
}
}
},
output(t)
},
count = 1,
while(x >= 1) {
t = selectIndice(x % 10),
x = (x-t) / 10,
n = n + t*count,
count = count * 10
},
output(n)
},
fun lsb(n) {
res = [],
k = n,
while(n > 0) {
p = n % 2,
res = res p,
n = (n - n % 2) / 2
},
select {
default {
foreach(i from res) {
if (res(i) == 1) {
res(i) = 0,
jump "break"
}
}
},
break {}
},
z = 0,
i = res.length - 1,
while(i >= 0) {
z = 2 * z,
z = z + res(i),
i = i - 1
},
output(k-z)
},
fun init_sort_tree[tree](arr) {
foreach(i from arr) {
h = { sum : 0, max : arr(i) },
tree = tree h
}
},
fun create_sort_tree[croisements,tree](arr) {
init_sort_tree(arr),
foreach(i from tree) {
update_sort_tree(i, arr(i))
}
},
fun update_sort_tree[croisements,arr,tree](i, diff) {
j = i,
select {
default {
while(i < tree.length) {
if (croisements(i) exists) {} else croisements(i) = [],
croisements(i) = croisements(i) j,
if (tree(i).max < diff) {
tree(i).max = diff
},
tree(i).sum = tree(i).sum + diff,
l = lsb(i),
if (l == 0)
{ jump "break" }
else
i = i + l
}
},
break {}
}
},
fun query_sort_tree[exceptions, croisements, arr,tree](start, end) {
i = end,
sum = 0,
max = tree(end).max,
select {
default {
while(i >= start) {
if (croisements(end) exists) {} else croisements(end) = [],
croisements(end) = croisements(end) i,
if (exceptions(i)) {} else {
if (tree(i).max > max) {
max = tree(i).max
},
sum = sum + tree(i).sum
},
l = lsb(i),
if (l == 0)
{ jump "break" }
else
i = i - l
}
},
break {}
},
output({ sum : sum, max : max })
},
tree = [],
arr = [1,2,6,4,2,6,7,3,9,1,4,6,3,1,2,5],
print("start"),
create_sort_tree(arr),
print(arr),
print(list@ToSequence(tree, ";")),
foreach(i from croisements) {
croisements(i) = croisements(i) "|"
},
exceptions = {},
foreach(i from tree) {
h = query_sort_tree(0, i),
print(h.sum ";" h.max)
},
foreach(i from croisements) {
print(i " = " list@ToSequence(croisements(i), ","))
},
// sort algorithm starting
h = query_sort_tree(0, tree.length - 1),
sum = h.sum,
max = h.max,
r = [],
// init sorted result
i = arr.length * arr.length,
while(i > 0) {
r = r 0,
i = i - 1
},
foreach(i from arr) {
s = toInt(getIndex(sum, arr(i)) * sum / max * arr.length * arr.length)),
r( s ) = arr(i)
},
foreach(i from r) {
if (r(i) == 0) {} else print(r(i) ",")
}
]>>]
此代码的输出显示：
- 输入列表：此列表项只有正值，并且该算法对于唯一和正值有效。
- 树列表
- 每个范围 [0,i] 的总和和最大值（当 0 <= i < n 时）
- 计算总和的方法（数组中索引的列表，然后是每个范围内树中的索引）
- 排序后的列表
start
1,2,6,4,2,6,7,3,9,1,4,6,3,1,2,5
[object Object];....
1;1
3;2
9;6
13;6
15;6
21;6
28;7
31;7
40;9
41;9
45;9
51;9
54;9
55;9
57;9
62;9
0 = 0,|,0
1 = 1,|,1,0
2 = 1,2,|,2,0
3 = 3,|,3,2,0
4 = 1,2,3,4,|,4,0
5 = 5,|,5,4,0
6 = 5,6,|,6,4,0
7 = 7,|,7,6,4,0
8 = 1,2,3,4,5,6,7,8,|,8,0
9 = 9,|,9,8,0
10 = 9,10,|,10,8,0
11 = 11,|,11,10,8,0
12 = 9,10,11,12,|,12,8,0
13 = 13,|,13,12,8,0
14 = 13,14,|,14,12,8,0
15 = 15,|,15,14,12,8,0
1,
2,
3,
4,
5,
6,
7,
9,
关注点
我学习了 Fenwick 树算法。我进行了讲解并展示了结果。我很好地理解了这个算法。尽管该算法需要线性时间，但检索排序列表元素的复杂度为 O(n^2)，因为我没有完全理解如何重现 ChatGPT 给我的代码。
历史
- 2022 年 12 月 26 日：初始版本