CSP-S 2026 第一轮 第 7 题：树状数组维护长度 n=16 的序列

题目

树状数组维护长度 $n=16$ 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ ）。

选项

• A. 3 和 4
• B. 4 和 4
• C. 3 和 5
• D. 4 和 3

答案

A

题解

答案是 A：3 和 4。

树状数组用 \(\operatorname{lowbit}(i)=i\&(-i)\) 决定下一个访问位置。

• 查询前缀和 sum(11)：每次令 \(i \leftarrow i-\operatorname{lowbit}(i)\)。

\[ 11\rightarrow10\rightarrow8\rightarrow0 \] 到 \(0\) 时停止，因此访问 11、10、8，共 3 个下标。

• 单点修改 add(3, x)：每次令 \(i \leftarrow i+\operatorname{lowbit}(i)\)。

\[ 3\rightarrow4\rightarrow8\rightarrow16\rightarrow32 \] 超过 \(n=16\) 时停止，因此访问 3、4、8、16，共 4 个下标。

记忆：查询减 lowbit，修改加 lowbit。