树状数组操作详解：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 = size
        self.tree = [0] * (size + 1)

    def lowbit(self, x):
        return x & -x

    def update(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += self.lowbit(index)

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.lowbit(index)
        return res

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

作者：bj3281