CSP-S 提高级 · CSP 2026 提高级第一轮 第 7 题

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

树状数组的两次操作都是"沿 lowbit 跳"：查询前缀和 sum(i) 是不断 i -= lowbit(i)，修改 add(i) 是不断 i += lowbit(i)。把 11 和 3 写成二进制，数一数跳了几次即可。

把两个操作的跳跃方向记反（查询往小跳、修改往大跳）；或数 11 时漏了最后一跳到 0 之前的那一步。

解析

本题考查树状数组（BIT）的下标跳跃规律。

树状数组的两条基本操作

记 lowbit(x) = x & (−x)，即 x 的二进制中最低位的 1 及其后的 0 组成的数。

sum(11)

11 = 1011₂，lowbit(11) = 1：

• 11 → 11 − 1 = 10
• 10 = 1010₂，lowbit = 2 → 10 − 2 = 8
• 8 = 1000₂，lowbit = 8 → 8 − 8 = 0（结束）

访问的下标：11, 10, 8 —— 共 3 个

add(3, x)

3 = 11₂，lowbit(3) = 1：

• 3 → 3 + 1 = 4
• 4 = 100₂，lowbit = 4 → 4 + 4 = 8
• 8 → 8 + 8 = 16
• 16 = 10000₂，lowbit = 16 → 16 + 16 = 32 > n = 16（结束，实际访问到 16 为止）

访问的下标：3, 4, 8, 16 —— 共 4 个

结论

sum(11) 访问 3 个下标，add(3, x) 访问 4 个下标，选 A（3 和 4）。

为什么这样跳

树状数组把区间 [i − lowbit(i) + 1, i] 的信息存在 c[i] 里：

• 查询时每次剥掉最低位的 1，就等于把"若干个不重叠区间"拼成 [1, i]，次数 = i 的二进制中 1 的个数；
• 修改时每次加上最低位的 1，命中所有"管辖到 i 的结点"，次数 = ⌊log₂n⌋ 量级。

因此本题也可以走捷径：11 的 popcount = 3，直接得 3 次。

记忆点

• 查询次数 = popcount(i)；修改次数 ≈ O(log n)（与 i 的位置有关）；
• 树状数组的容量通常是 2 的幂（本题 n = 16），理解"16 → 32 越界停止"这一点；
• 与线段树对比：BIT 常数小、代码短，但只能维护可减信息（如和、异或），不能维护 min/max。