题解 | #区间取反与单点求值#

题目链接

区间取反与单点求值

题目描述

给定一个长度为 $n$ 的 01 字符串，我们需要实现一个数据结构来支持以下两种操作：

区间取反：将区间 $[l, r]$ 内的所有字符进行取反操作（0 变为 1，1 变为 0）。
单点查询：查询下标为 $x$ 的字符的值。

输入:

第一行包含两个整数 $n$ 和 $m$ ，分别表示 01 串的长度和操作的次数。
第二行是一个长度为 $n$ 的 01 字符串。
接下来 $m$ 行，每行描述一个操作。格式为 1 l r 或 2 x。

输出:

对于每个查询操作，输出一行，表示对应下标的字符值。

解题思路

本题要求我们维护一个可以进行区间修改和单点查询的数据结构。对于这类问题，一个非常有效的方法是使用树状数组结合差分思想。

核心思路如下：一个数被取反奇数次，结果等于取反一次；被取反偶数次，结果等于没有取反。这个性质正好对应了异或（XOR）运算的性质： $x \oplus 1 \oplus 1 = x$ 。因此，我们可以将取反操作看作是与 1 进行异或。

差分数组：

我们定义一个差分数组 $d$ ，用它来记录每个点相比前一个点变化的次数。当我们对区间 $[l, r]$ 进行取反时，只有两个点的状态会发生变化：
- $l$ 点开始被取反，它与 $l-1$ 点的关系改变了。
- $r+1$ 点不再被取反，它与 $r$ 点的关系也改变了。
所以，一次区间 $[l, r]$ 的取反操作，等价于在差分数组上进行两次单点修改： $d[l] \leftarrow d[l] \oplus 1$ 和 $d[r+1] \leftarrow d[r+1] \oplus 1$ 。
树状数组维护差分前缀和：

一个点 $x$ 的最终值，取决于它的初始值以及它被取反的总次数。而点 $x$ 被取反的总次数，恰好是差分数组 $d$ 的前缀和 $\sum_{i=1}^{x} d[i]$ （这里的求和是异或意义下的）。

为了快速求出差分数组的前缀异或和，我们可以使用树状数组来维护。

综上，整个流程如下：

初始化：读入原始 01 串。创建一个大小为 $n+1$ 的树状数组，所有元素初始化为 $0$ 。
区间取反 l r：在树状数组上执行两次单点更新：add(l, 1) 和 add(r + 1, 1)。
单点查询 x：查询树状数组中 $x$ 的前缀异或和 query(x)，这个结果就是 $x$ 被取反的总次数。用原始值 a[x] 与这个次数进行异或，即得到最终答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
vector<int> tr;
vector<int> a;

int lowbit(int x) {
    return x & -x;
}

void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] ^= k;
    }
}

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res ^= tr[i];
    }
    return res;
}

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

    int m;
    cin >> n >> m;
    
    string s;
    cin >> s;
    
    a.resize(n + 1);
    tr.resize(n + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        a[i + 1] = s[i] - '0';
    }
    
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            add(l, 1);
            if (r + 1 <= n) {
                add(r + 1, 1);
            }
        } else {
            int x;
            cin >> x;
            cout << (a[x] ^ query(x)) << "\n";
        }
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static int n;
    static int[] tr;
    static int[] a;

    static int lowbit(int x) {
        return x & -x;
    }

    static void add(int x, int k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tr[i] ^= k;
        }
    }

    static int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res ^= tr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();

        a = new int[n + 1];
        tr = new int[n + 1];

        for (int i = 0; i < n; i++) {
            a[i + 1] = s.charAt(i) - '0';
        }

        while (m-- > 0) {
            int op = sc.nextInt();
            if (op == 1) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                add(l, 1);
                if (r + 1 <= n) {
                    add(r + 1, 1);
                }
            } else {
                int x = sc.nextInt();
                System.out.println(a[x] ^ query(x));
            }
        }
    }
}

import sys

def lowbit(x):
    return x & -x

def add(x, k):
    while x <= n:
        tr[x] ^= k
        x += lowbit(x)

def query(x):
    res = 0
    while x > 0:
        res ^= tr[x]
        x -= lowbit(x)
    return res

# 读取输入
lines = sys.stdin.readlines()
n, m = map(int, lines[0].split())
s = lines[1].strip()
a = [0] * (n + 1)
tr = [0] * (n + 1)

for i in range(n):
    a[i + 1] = int(s[i])

for i in range(m):
    parts = list(map(int, lines[i + 2].split()))
    op = parts[0]
    
    if op == 1:
        l, r = parts[1], parts[2]
        add(l, 1)
        if r + 1 <= n:
            add(r + 1, 1)
    else:
        x = parts[1]
        result = a[x] ^ query(x)
        print(result)

算法及复杂度

算法：树状数组 + 差分
时间复杂度：共有 $m$ 次操作，每次操作（修改或查询）在树状数组上的时间复杂度均为 $\mathcal{O}(\log n)$ 。因此，总时间复杂度为 $\mathcal{O}(n + m \cdot \log n)$ ，其中 $n$ 为初始化字符串的开销。
空间复杂度：需要一个数组存储原始 01 串，以及一个树状数组，所以空间复杂度为 $\mathcal{O}(n)$ 。