【题目描述】
NK 中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。由于 NK 中学的学生很多，在火车开之前必须清点好人数。
初始时，火车上没有学生。当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第 m 节车厢时，他想知道前 m 节车厢上一共有多少学生，但是他没有调头往回走的习惯。也就是说每次当他提问时，m 总会比前一次大。
【输入】
第一行两个整数 n,k，表示火车共有 n 节车厢以及 k 个事件。
接下来有 k 行，按时间先后给出 k 个事件，每行开头都有一个字母 A，B 或 C。
如果字母为 A，接下来是一个数 m，表示年级主任现在在第 m 节车厢；
如果字母为 B，接下来是两个数 m,p，表示在第 m 节车厢有 p 名学生上车；
如果字母为 C，接下来是两个数 m,p，表示在第 m 节车厢有 p 名学生下车。
学生总人数不会超过 105 。
【输出】
对于每个 A ，输出一行，一个整数，表示年级主任的问题的答案。
【输入样例】
10 7
A 1
B 1 1
B 3 1
B 4 1
A 2
A 3
A 10
【输出样例】
0
1
2
3
【提示】
数据范围与提示：
对于 30% 的数据，1≤n,k≤10^4 ，至少有 3000 个 A；
对于 100% 的数据，1≤n≤5×10^5,1≤k≤10^5 ，至少有 3×10^4 个 A。
一、 题目分析
【题目模型】 一列火车有 n 节车厢，初始全空。有 k 次动态事件交替发生：
-
事件 B/C： 第 m 节车厢有 p 名学生上车（增加）或下车（减少）。
-
事件 A： 年级主任走到第 m 节车厢，提问：前 m 节车厢（即区间 [1,m]）一共有多少学生？
【数据规模】 车厢数 n≤5×10^5，事件数 k≤10^5。 如果在 1s 的时限内使用 O(n) 的暴力累加来回答主任的提问，当查询次数逼近 10^5 时，总运算量将高达 5×10^10，必定超时。我们需要一种支持 O(logn) 级别动态修改和查询的数据结构。
二、 思考过程
题目中有一句非常耐人寻味的话：
“他没有调头往回走的习惯。也就是说每次当他提问时，m 总会比前一次大。”
萌新的直觉： 很多同学看到这句话，第一反应是：“既然主任一直往前走，那我是不是不需要复杂的数据结构？只要拿一个变量 sum，主任走到哪，我就一路加过去就行了？”
破局点： 不行！请注意题目的另一句话：“每节车厢随时都有可能有同学上下”。 主任虽然一直在往右走（查询的右端点单调递增），但是学生完全有可能在他已经走过去的、身后的车厢里上下车！如果只用一个标量记录，身后的动态修改就彻底丢失了。
这正是必须使用树状数组的原因：我们需要一个能够随时响应任意位置的修改，并能极速求出动态前缀和的武器。
三、 解题思路与算法设计
抛开故事外衣，这就是一个长度为 n 的全零数组，支持以下三种操作：
核心引擎 lowbit： lowbit(x)=x&(-x)，用于提取x二进制最低位的1所代表的整数，是树状数组向上汇报和向下查询的跳跃步长。
学生上车/下车（单点修改）：
-
调用update(m, p)表示第m节车厢增加p人。
-
调用update(m, -p)表示第m节车厢减少p人。
-
物理操作：顺着 i+=lowbit(i)，将所有管辖了该车厢的“上级节点”全部同步修改。
主任提问（前缀查询）：
-
调用query(m)。
-
物理操作： 顺着 x-=lowbit(x)，将多个互不重叠的管辖区间的总人数累加，瞬间拼凑出前m节车厢的总人数。
四、 时空复杂度分析
-
时间复杂度： 每次update和query都在树状数组的层级上跳跃，单次耗时O(logn)。总共有k 个事件，总体时间复杂度为O(klogn)。对于10^5的操作量，耗时不到数毫秒，极速 AC。
-
空间复杂度： 仅需开辟一个长度为 n+1 的树状数组 c，总体空间复杂度为 O(n)。
五、 易错点总结
极其健壮的字符读入： 题目每行以字母 A, B, C 开头。实战中极度不建议使用 scanf("%c") 或 gets，因为老旧评测机的行末常常带有隐形的回车符 \\r\\n，极易导致读入错位。标准解法： 使用 char thing; cin >> thing;，C++ 的 cin 会自动安全地过滤掉所有空白字符（包括空格和换行）。
局部变量的整洁性： 在 if-else 分支中按需声明局部变量 int m, p;，用完即毁，防止变量污染外层逻辑。
全员long long： 尽管题目提示学生总人数不超过10^5，但在算法竞赛中，只要遇到“区间求和”、“树状数组”，一律使用long long声明底层数组和返回值，这是百利而无一害的好习惯。
六、 完整代码
//单点修改 区间查询
#include <iostream>
using namespace std;
typedef long long ll;
int n,k;
ll c[500010];//树状数组
//返回x二进制表示下最低位1所代表的整数
int lowbit(int x){
return x&(-x);
}
//树状数组更新操作 原第x节车厢增加val学生
//对应树状数组所有包含x的项都增加val学生
void update(int x,ll val){
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=val;
}
//查询前x节车厢总共多少学生
ll query(int x){
ll ret=0ll;//存前缀和
while(x){//c[x]包含了多节车厢
ret+=c[x];
//减去c[x]包含的项数，精准跳跃到上一个相邻不重叠的管辖区间
x-=lowbit(x);
}
return ret;
}
int main(){
//io加速
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
//总共k个事件
while(k–){
char thing;//事件
cin>>thing;
if(thing=='A'){//表示年级主任现在在第m节车厢
int m;
cin>>m;
cout<<query(m)<<"\\n";
}
//表示在第m节车厢有p名学生上车
else if(thing=='B'){
int m,p;
cin>>m>>p;
update(m,p);
}
//表示在第m节车厢有p名学生下车
else{
int m,p;
cin>>m>>p;
update(m,-p);
}
}
return 0;
}
