简单题（信息学奥赛一本通- P1539）

题目来源：CQOI 2006

有一个 n 个元素的数组，每个元素初始均为 0。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1 变 0（操作 1），要么询问某个元素的值（操作 2）。

例如当 n=20 时，10 条指令如下：

第一行包含两个整数 n,m，表示数组的长度和指令的条数；

以下 m 行，每行的第一个数 t 表示操作的种类：

若 t=1，则接下来有两个数 L,R，表示区间 [L,R] 的每个数均反转；

若 t=2，则接下来只有一个数 i，表示询问的下标。

每个操作 2 输出一行（非 0 即 1），表示每次操作 2 的回答。

数据范围与提示：

对于 50% 的数据，1≤n≤10^3,1≤m≤10^4 ；

对于 100% 的数据，1≤n≤10^5,1≤m≤5×10^5 ，保证 L≤R。

一、 题目分析

【题目大意】给定一个长度为n的数组，初始所有元素均为0。系统会给出m条指令，包含两种操作：

1. 操作 1（区间修改）：给定区间[L,R]，将区间内的数字反转（0 变 1，1 变 0）。

2. 操作 2（单点查询）：给定下标i，查询当前位置的值。

【数据范围】1≤n≤10^5,1≤m≤5×10^5。 极限情况下有50万次操作，要求算法的时间复杂度必须严格控制在 O(MlogN) 级别，否则必定超时。

二、 思考过程

1. 反转操作的数学本质是什么？在二进制的世界里，状态的“反转”等价于“加上1，然后对2取模”。也就是说，如果一个位置被翻转了k次，它的最终状态就是 k%2。

2. 如何高效处理“区间加法”？如果在原数组上直接跑for循环，时间复杂度是O(N)，面对50 万次指令会直接崩溃。此时必须引入差分数组。 对于差分数组d，给原数组区间[L,R] 加上 1，等价于在差分数组上做两次单点修改：d[L]+=1和d[R+1]-=1。

3. 如何高效处理“单点查询”？原数组第i个位置的值，等于差分数组d从1到i的前缀和。

经过这三步推演，问题被彻底剥去了伪装：我们需要一个数据结构，能够极速支持**“单点修改”和“查询前缀和”。这正是树状数组的绝对主场。

三、 解题思路

我们将原问题完全转换为树状数组的标准模板：

• 建树阶段：由于初始数组全为0，差分数组也全为0，所以不需要任何预处理，直接开一个初始值为0的树状数组即可。

• 修改阶段：遇到指令1，读入L和R。调用update(L,1)和update(R+1,-1)。

• 查询阶段：遇到指令2，读入i。调用query(i)获取差分数组的前缀和（即该位置被翻转的总次数），然后输出query(i)%2即可。

四、 算法设计

• lowbit函数：x&(-x)，用于快速定位树状数组的管辖区间。

• update函数：通过x+=lowbit(x)向上攀升，更新所有包含该单点的父节点。

• query函数：通过x-=lowbit(x)向下聚拢，快速累加出前缀和。

• IO优化：使用cin.tie(0)解除流绑定，确保在5×10^5级别的数据输入下不被卡常。

五、 时空复杂度分析

• 时间复杂度：

  • 树状数组的每次update和query都是严格的O(logN)。

  • 共有M条指令，总体时间复杂度为O(MlogN)。在 10^5 级别的数据下，最大计算量仅千万级别，100ms 内即可瞬间跑完。

• 空间复杂度：

  • 只需开辟一个大小为N+1的树状数组c[]，空间复杂度为O(N)。极致轻量。

六、 易错点总结

1. 数组越界防范：当反转的区间到达数组最右端（R=n）时，update(R+1,-1)会试图访问 n+1 的位置。但由于update的内部循环条件是while(x<=n)，参数n+1传进去后会直接跳过循环，天然免疫了越界报错。

2. 取模负数陷阱：C++中负数取模依然是负数。本题中由于是累加区间覆盖次数，前缀和绝对不可能为负，所以写update(R+1,-1)是安全的。但更严谨的竞赛技巧是：既然只关心奇偶性，加1和减1效果相同，可以直接写成update(R+1,1)，从根源上杜绝负数的出现。

3. 滥用线段树：本题用线段树完全可以做，但线段树常数极大，容易在极限数据下被卡。能用树状数组解决的差分问题，绝不用线段树。

七、 题解

本题是利用“差分思想”将区间操作降维的极佳例题。通过将“区间反转”转化为“区间加法”，再利用差分将其转化为“单点修改”，最终用常数极小、代码极短的树状数组完成了对暴力算法的降维打击。

八、 完整代码

//区间修改 单点查询 翻转可以理解为+1然后对2取模 #include <iostream> using namespace std; int n,m; int a[500010];//原数组 每个元素均为0 int d[500010];//差分数组 int c[500010];//树状数组 //返回x二进制表示下最低位的1所代表的整数 int lowbit(int x){ return x&(-x); } //树状数组更新操作 void update(int x,int k){ //向上更新所有包含x的大区间 while(x<=n){ c[x]+=k; x+=lowbit(x); } } //树状数组查询 int query(int x){ int ret=0;//记录前缀和 while(x>0){ ret+=c[x]; x-=lowbit(x); } //核心：总翻转次数对2取模，得出最终的0或1 return ret%2; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ a[i]=0;//原数组 每个元素均为0 d[i]=a[i]-a[i-1];//差分数组 update(i,d[i]);//更新树状数组 } //m组指令 while(m--){ int t; cin>>t; if(t==1){//l-r区间翻转 int l,r; cin>>l>>r; update(l,1); update(r+1,-1); } else{//查询 int i; cin>>i; cout<<query(i)<<"\n"; } } return 0; }