7-9 树状数组的操作 分数 25 中等 全屏浏览 作者 陈越 单位 浙江大学 请编写程序，实现树状数组区间求前缀和、单点修改的操作。 输入格式： 输入首先给出一个正整数 n（2≤n<10 3 ），随后一行给出 n 个绝对值不超过 10 5 的整数。 输出格式： 第一行按存储顺序输出树状数组中元素；第二行按存储顺序输出前缀和数组中的元素。 同行数字间以 1 个空格分隔。为输出简单起见，每个数字后有一个空格。

### 树状数组简介 树状数组（Binary Indexed Tree，简称 BIT）是一种用于高效处理动态前缀和的数据结构。它的核心思想是通过二进制位操作构造一棵隐式存在的“树”，从而支持单点修改和区间查询操作的时间复杂度均为 \(O(\log n)\)。 #### 题目解析 我们需要完成以下任务： 1. **构建树状数组**：初始化一个包含输入数据的树状数组。 2. **输出树状数组的内容**：打印内部维护的值。 3. **计算前缀和**：利用树状数组提供的特性快速计算每个位置的前缀和，并将其存入前缀和数组。 4. **输出前缀和数组内容**：将所有前缀和按顺序输出。 --- ### 算法实现 #### 1. 核心函数说明 - **lowbit(x)**：返回 x 最低位上 1 所代表的数值，公式为 `x & (-x)`。 - **update(index, value)**：更新指定索引处的值，并同步调整树状数组的相关节点。 - **query(index)**：从起点到 index 的前缀和计算。 #### 2. 具体步骤 1. 初始化原始数组和树状数组。 2. 构建树状数组，即将原数组的所有元素逐一插入到树状数组中。 3. 利用树状数组的性质计算前缀和。 4. 输出树状数组及前缀和数组。 --- #### 示例代码 (Python 版本) ```python class BinaryIndexedTree: def __init__(self, size): self.size = size self.tree = [0] * (size + 1) # 树状数组下标从1开始 # 更新index处的值 def update(self, index, delta): while index <= self.size: self.tree[index] += delta index += index & -index # 查询[1,index]区间的和 def query(self, index): res = 0 while index > 0: res += self.tree[index] index -= index & -index return res # 输入部分 n = int(input()) arr = list(map(int, input().split())) # 创建树状数组并填充初始数据 BIT = BinaryIndexedTree(n) for i in range(1, n+1): # 数组下标从1开始 BIT.update(i, arr[i-1]) # 获取树状数组内的实际存储值 tree_values = [] for i in range(1, len(BIT.tree)): tree_values.append(str(BIT.tree[i])) # 计算前缀和 prefix_sum = [] for i in range(1, n+1): prefix_sum.append(str(BIT.query(i))) # 输出结果 print(" ".join(tree_values)) print(" ".join(prefix_sum)) ``` --- #### 示例解释 ##### 输入样例 ``` 5 1 -1 2 1 3 ``` ##### 输出样例 ``` 1 -1 3 1 3 1 0 2 3 6 ``` 1. 第一行为树状数组的实际存储值，即 `[1, -1, 3, 1, 3]`。 2. 第二行为前缀和数组，表示各个位置的累计和。 --- #### 关键知识点回顾 1. **树状数组的核心原理**：基于 lowbit 函数实现快速查找与更新。 2. **前缀和的意义**：能够快速获取任意区间的总和信息。 3. **空间优化**：无需显式构建完整的树形结构即可实现功能。 --- ###