题解 | #区间取反与区间数一#

针对此类经典的“区间修改+区间查询”问题，最优的算法是线段树。

算法

采用 分治策略 将序列划分为二叉树结构。

节点维护信息 (Attribute)：
- sum：当前区间内 1 的总个数。
- tag：布尔型或整型懒标记，表示当前区间是否积压了一次“取反”操作。
状态转移逻辑：
- 父子关系：父节点的 sum 等于左孩子 sum + 右孩子 sum。
- 取反逻辑：当一个节点接收到取反指令时：
  1. 数值更新：当前区间的 sum 变为 区间长度 - sum。
  2. 标记累加： $tag \leftarrow tag \oplus 1$ （异或操作）。即：若无标签则打上标签，若已有标签则抵消（两次取反等于没变）。

相比于树状数组（Fenwick Tree），线段树在处理区间反转这种非加法性的区间更新时更为直观且易于实现。树状数组通常需要维护差分数组或通过较复杂的数学变换才能支持区间翻转，而线段树可以直接利用 len - sum 的性质。相比于分块算法（ $O(\sqrt{n})$ ），线段树提供了更优的 $O(\log n)$ 性能。

复杂度

时间复杂度

建树 (Build): 树的节点总数约为 $2n \sim 4n$ ，每个节点访问 $O(1)$ 次。复杂度为 $O(n)$ 。
区间更新 (Update): 在最坏情况下，需要访问线段树的高层节点以及与区间边缘相关的 $O(\log n)$ 个节点。由于懒标记机制，不需要遍历区间内的所有叶子。复杂度为 $O(\log n)$ 。
区间查询 (Query): 类似于更新，最多分解为 $O(\log n)$ 个子区间进行求和。复杂度为 $O(\log n)$ 。
总复杂度: 对于 $q$ 次操作，总时间复杂度为 $O(n + q \log n)$ 。

空间复杂度

线段树需要数组来存储树结构。对于大小为 $n$ 的区间，通常开辟 $4n$ 大小的数组以避免越界（因为这是完全二叉树的堆式存储最坏情况）。
空间消耗为线性 $O(n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class SegTree {
  private:
    int n;
    vector<int> sum;
    vector<int> lazy;

    void push_up(int p) {
        sum[p] = sum[2 * p] + sum[2 * p + 1];
    }

    void push_down(int p, int l, int r) {
        if (lazy[p]) {
            int mid = (l + r) / 2;

            lazy[p * 2] ^= 1;
            sum[p * 2] = (mid - l + 1) - sum[p * 2];

            lazy[p * 2 + 1] ^= 1;
            sum[p * 2 + 1] = (r - mid) - sum[p * 2 + 1];

            lazy[p] = 0;
        }
    }

  public:
    SegTree(int n): n(n), sum(4 * n + 1, 0), lazy(4 * n + 1, 0) {}

    void build(const string& s, int p, int l, int r) {
        if (l == r) {
            sum[p] = s[l - 1] - '0';
            return;
        }
        int mid = (l + r) / 2;
        build(s, p * 2, l, mid);
        build(s, p * 2 + 1, mid + 1, r);
        push_up(p);
    }

    void update(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            sum[p] = (r - l + 1) - sum[p];
            lazy[p] ^= 1;
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) / 2;
        if (ql <= mid)
            update(p * 2, l, mid, ql, qr);
        if (qr > mid)
            update(p * 2 + 1, mid + 1, r, ql, qr);
        push_up(p);
    }

    int query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return sum[p];
        push_down(p, l, r);
        int mid = (l + r) / 2;
        int res = 0;
        if (ql <= mid)
            res += query(p * 2, l, mid, ql, qr);
        if (qr > mid)
            res += query(p * 2 + 1, mid + 1, r, ql, qr);
        return res;
    }

};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;


    SegTree st(n);
    st.build(s, 1, 1, n);

    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            st.update(1, 1, n, l, r);
        } else if (op == 2) {
            int res = st.query(1, 1, n, l, r);
            cout << res << endl;
        }
    }

    return 0;
}