1. 一个大小为 8 的树状数组，执行“在下标 3 处单点加”时，会依次更新哪些下标？

{{ select(1) }}

• {3, 4, 8}
• {3, 6, 8}
• {3, 7, 8}
• 只有 {3}

2. 下列任务中，不能用单调栈在 O(n) 内直接求解的是？

{{ select(2) }}

• 每个元素左边第一个比它小的数
• 每个元素右边第一个比它大的数
• 任意给定区间 [l,r] 的元素之和（多次询问、带单点修改）
• 每个元素作为最小值能向两侧扩展的最大区间

3. 多项式哈希 h = Σ s[i]·base^(n−i) (mod p) 中，最不容易被构造数据卡掉的参数选择是？

{{ select(3) }}

• base = 1，p = 2^64（自然溢出）
• base = 256，p = 256
• base、p 均为公开固定的小数（如 base=10, p=97）
• base、p 取两个较大的随机质数，并采用双哈希

4. 关于“普通前缀和数组”与“树状数组”，下列说法正确的是？

{{ select(4) }}

• 两者都支持 O(1) 单点修改后立即 O(1) 区间查询
• 普通前缀和单点修改后需 O(n) 重建，树状数组单点修改 O(log n)
• 树状数组无法做前缀和查询
• 普通前缀和支持动态修改，树状数组只能静态查询

5. 序列 a = [1, 3, 2, 5, 4]，窗口长度 k = 3。从左到右每个窗口的最大值依次是？

{{ select(5) }}

• 3 5 5
• 3 3 5
• 1 2 4
• 5 5 5

6. 用 h[i] = h[i−1]·base + s[i]（h[0]=0）做前缀哈希，base = 10，串 s 的数字依次为 3, 1, 4。子串 s[2..3]（即“1 4”）的哈希值为？

{{ select(6) }}

• 41
• 14
• 314
• 11

7. 在树状数组上查询前缀和 query(7) 时，会依次累加哪些下标处的值？

{{ select(7) }}

• {7, 6, 4}
• {7, 6, 5, 4}
• {7, 3, 1}
• {1, 2, 4}

8. 单调栈处理 n 个元素时整体复杂度是 O(n)，最准确的解释是？

{{ select(8) }}

• 因为只有一层循环
• 因为栈最多存 n 个元素
• 均摊分析：每个元素一生中至多入栈一次、出栈一次，总操作 ≤ 2n
• 因为每步都是 O(1)，所以一定 O(n)

9. 仅用一个树状数组，想支持“区间 [l,r] 同时加上一个值”与“单点查询某位置当前值”，应采用的技巧是？

{{ select(9) }}

• 把树状数组开两倍大
• 维护差分数组的树状数组：区间加化为两个单点改，单点查化为前缀和
• 改用单调队列
• 无法实现，必须用线段树

10. 形如 dp[i] = max{ dp[j] : i−k ≤ j ≤ i−1 } + w[i] 的转移之所以能用单调队列优化到 O(n)，关键原因是？

{{ select(10) }}

• w[i] 单调递增
• 决策区间 [i−k, i−1] 的左右端点都随 i 单调右移，被更优值支配的决策永不再用
• dp 数组本身单调
• k 必须等于 1