树状数组的操作问题--Python

一、问题引入

请编写程序，实现树状数组区间求前缀和、单点修改的操作。

输入格式：
输入首先给出一个正整数 n（2≤n<10^3
），随后一行给出 n 个绝对值不超过 10^5
的整数。

输出格式：
第一行按存储顺序输出树状数组中元素；第二行按存储顺序输出前缀和数组中的元素。
同行数字间以 1 个空格分隔。为输出简单起见，每个数字后有一个空格。

输入样例：

15
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

输出样例：

15 29 13 54 11 21 9 92 7 13 5 22 3 5 1
15 29 42 54 65 75 84 92 99 105 110 114 117 119 120

二、解题步骤

1.思维导图

2.解题步骤

1. 理解树状数组结构
   ◦ 树状数组是一种高效维护前缀和的数据结构
   ◦ 支持单点更新和前缀查询，时间复杂度均为O(log n)
2. 实现核心操作
   ◦ lowbit(x): 计算x的最低有效位，用于确定更新和查询的路径
   ◦ update(index, value): 在指定位置增加一个值，并更新相关节点
   ◦ query(index): 查询从1到index的前缀和
3. 处理输入输出
   ◦ 读取数组大小n和n个整数
   ◦ 构建树状数组并初始化
   ◦ 输出树状数组的存储内容（注意从索引1开始）
   ◦ 计算并输出前缀和数组
4. 边界条件处理
   ◦ 检查输入数组长度是否匹配
   ◦ 处理可能的输入错误

三、代码实现

1.代码

class FenwickTree:def __init__(self, size):self.size = sizeself.tree = [0] * (size + 1)def lowbit(self, x):return x & -xdef update(self, index, value):while index <= self.size:self.tree[index] += valueindex += self.lowbit(index)def query(self, index):res = 0while index > 0:res += self.tree[index]index -= self.lowbit(index)return resdef main():try:# 读取输入n = int(input())nums = list(map(int, input().split()))# 检查输入是否合法if len(nums) != n:print("错误：输入数组长度不匹配。")return# 初始化树状数组fenwick_tree = FenwickTree(n)for i in range(1, n + 1):fenwick_tree.update(i, nums[i - 1])# 输出树状数组print(" ".join(map(str, fenwick_tree.tree[1:])) + " ")# 计算前缀和并输出prefix_sum = [fenwick_tree.query(i) for i in range(1, n + 1)]print(" ".join(map(str, prefix_sum)) + " ")except Exception as e:print("错误：输入格式不正确。")# 调用主函数
if __name__ == "__main__":main()

2.复杂度分析

时间复杂度：
■ 初始化：O(n log n) - 需要n次update操作
■ 查询前缀和：O(log n)每次查询
■ 输出阶段：O(n log n) - 需要n次query操作

空间复杂度：O(n) - 存储树状数组和前缀和数组

四、个人总结

通过本次实验，我深入理解了树状数组的原理与应用。在实现过程中，我最初对lowbit操作的理解仅停留在公式层面，但通过手动模拟更新和查询过程，逐渐掌握了其本质——通过二进制位的跳转高效维护前缀信息。

当首次看到树状数组的存储内容输出时，我发现它并非简单存储原数组，而是通过巧妙的层次结构组织数据。在调试前缀和计算时，曾因索引从1开始的特性导致错误，这个教训让我意识到边界条件的重要性。

相比暴力计算前缀和，树状数组的O(logn)时间复杂度优势在多次操作时尤为明显，这使我对算法优化的价值有了更直观的认识。通过对比标准前缀和数组的输出，我验证了实现的正确性，同时也发现树状数组虽然查询效率高，但需要额外的存储空间，这让我体会到时空权衡的设计思想。最让我受益的是将抽象的数据结构转化为具体代码的过程，这不仅巩固了位运算的知识，也培养了我将数学思想工程化的能力。