把灯的开关状态看成 0/1 数组，区间翻转时用 `区间长度 - 当前开灯数` 更新节点，再用懒标记维护整段翻转。
OJ: luogu
题目 ID: P2846
难度:普及/提高-
标签:线段树懒标记区间翻转区间求和
日期: 2026-06-21 02:13
题意
有 N 盏灯，初始全部关闭。
接下来有 M 次操作：
0 l r：把区间[l, r]内每盏灯的状态翻转1 l r：查询区间[l, r]内当前有多少盏灯是打开的
对于每个查询操作输出答案。
思路
先看一个最朴素的模拟版本：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：直接用数组维护每盏灯当前是否打开。
// 区间翻转时逐个异或，区间查询时逐个统计。
const int MAXN = 100000 + 5;
int n, m;
int light_arr[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 0) {
for (int i = l; i <= r; i++) {
light_arr[i] ^= 1;
}
} else {
int ans = 0;
for (int i = l; i <= r; i++) {
ans += light_arr[i];
}
cout << ans << '\n';
}
}
return 0;
}brute.cpp 直接把每盏灯的状态放在数组里：
- 翻转时逐个异或
1 - 查询时逐个累加
这个做法很直观，但一次区间操作最坏要扫完整段，所以肯定过不了大数据。
优化时，把灯的状态看成一个 0/1 数组，然后交给线段树维护。
对于线段树的某个节点区间 [l, r]，只维护一件事：
- 这段区间内现在有多少盏灯是开的
这样当整段翻转时，就不用递归到底了，直接根据补集关系更新：
新的开灯数 = 区间长度 - 原来的开灯数
同时打一个懒标记，表示这段区间的翻转还没有传给子节点。
由于“翻转两次等于不翻”，这个懒标记只需要记录奇偶性，所以用 0/1 异或维护即可。
于是：
- 区间翻转：整段命中就直接改节点并打标记
- 区间查询：必要时先下传标记，再递归左右儿子
这就是标准的“区间翻转 + 区间求和”线段树模型。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n, m;
int seg[MAXN << 2];
int lazy_rev[MAXN << 2];
void push_up(int u) {
seg[u] = seg[u << 1] + seg[u << 1 | 1];
}
void apply_reverse(int u, int l, int r) {
seg[u] = (r - l + 1) - seg[u];
lazy_rev[u] ^= 1;
}
void push_down(int u, int l, int r) {
if (lazy_rev[u] == 0 || l == r) {
return;
}
int mid = (l + r) >> 1;
apply_reverse(u << 1, l, mid);
apply_reverse(u << 1 | 1, mid + 1, r);
lazy_rev[u] = 0;
}
void update(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
apply_reverse(u, l, r);
return;
}
push_down(u, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(u << 1, l, mid, ql, qr);
}
if (qr > mid) {
update(u << 1 | 1, mid + 1, r, ql, qr);
}
push_up(u);
}
int query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return seg[u];
}
push_down(u, l, r);
int mid = (l + r) >> 1;
int ans = 0;
if (ql <= mid) {
ans += query(u << 1, l, mid, ql, qr);
}
if (qr > mid) {
ans += query(u << 1 | 1, mid + 1, r, ql, qr);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 0) {
update(1, 1, n, l, r);
} else {
cout << query(1, 1, n, l, r) << '\n';
}
}
return 0;
}复杂度
每次修改或查询都在线段树上进行。
单次操作复杂度：
总时间复杂度：
空间复杂度：
总结
这题的核心只有一句话：
整段翻转后，开灯数 = 区间长度 - 原开灯数
一旦抓住这个关系，懒标记线段树就非常自然了。