#6687. AtCoder B - Fenwick Tree
-
ID: 6687
传统题
1000ms
256MiB
尝试: 1
已通过: 1
难度: 10
上传者:
hantianliang
标签> AtCoder B - Fenwick Tree
AtCoder B - Fenwick Tree
一、题目翻译
题目描述
给定一个长度为 N 的数组：
需要处理 Q 次操作。
操作有两种类型：
类型0：单点修改
格式：
0 p x
表示：
将：
增加：
x
即：
类型1：区间求和
格式：
1 l r
表示：
输出：
注意：
右端点 r 不包含。
也就是：
查询：
[l,r)
二、数据范围分析
1 ≤ N,Q ≤ 500000
数组长度：
50万
操作次数：
50万
如果暴力：
修改
单点修改：
O(1)
| 测试点编号 | N ≤ | Q ≤ | 难度层级 | 特殊性质 | 设计目的 |
|---|---|---|---|---|---|
| 1 | 5 | 弱数据 | 单元素、正负增量 | 检查最小规模、同一位置多次修改 | |
| 2 | 3 | 7 | 小数组、边界查询 | 覆盖 [0,N)、单点区间、首元素更新 |
|
| 3 | 5 | 8 | 全 0、空区间、末尾更新 | 检查 l=r 输出 0，以及 0 值初始化 |
|
| 4 | 6 | 10 | 正常数据 | 初值含负数、抵消更新 | 检查负数求和和修改后变为 0 的情况 |
| 5 | 8 | 严格递增、首尾下标 | 覆盖首尾位置更新、单元素区间和多段查询 | ||
| 6 | 16 | 12 | 正常偏强 | 2 的幂规模、Fenwick 边界 | 覆盖树状数组常见边界、前半/后半区间 |
| 7 | 4 | 8 | 极限数据 | long long 大数、正负抵消 |
检查是否使用 64 位整数，避免 int 溢出 |
| 8 | 10 | 15 | 极限综合 | 多次交错修改查询、混合正负 | 检查连续操作后的状态维护与综合正确性 |