wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

可持久化线段树

树链剖分

平衡树

FHQ-Treap

珂朵莉树

分块

位分块

[[ item.c ]]

位分块

## 位分块算法
位分块有的地方称为位图
### 位分块的成员函数
![](/media/content_img/bitblock01.png)

### 求区间内有多少个连续的 0/1
![](/media/content_img/bitblock02.png)

## 位分块算法实现
**结构体定义**
```bash
constexpr int B = 16;
constexpr int MASK = (1 << B) - 1;

struct Bitset {
    vector<u32> dat;

Bitset(int n = (MASK + 5)) {
        dat.resize(n);
        dat.assign(n, 0);
    }

Bitset(const string &S) {
        dat.assign(MASK + 5, 0);
        for (int i = 0; i < S.size(); i++) {
            dat[i / B] |= (S[i] - '0') << (i % B);
        }
    }

Bitset slice(int l, int len) {
        int bn = len / B, bl = l / B, bit = l % B;
        Bitset res(bn + 1);
        // l % B 表示在块内的偏移量
        for (int i = 0; i <= bn; i++) {
            res.dat[i] = dat[bl+i] >> bit | dat[bl+i+1] << (B - bit) & MASK;
        }
        return res;
    }

void flip(int l, int r) {
        int bl = l / B, br = r / B;
        if (bl == br) {
            for (int i = l % B; i <= r % B; i++) {
                dat[bl] ^= (1 << i);
            }
            return;
        }
        for (int i = l % B; i < B; i++) dat[bl] ^= (1 << i);
        for (int i = bl + 1; i < br; i++) dat[i] ^= MASK;
        for (int i = 0; i <= r % B; i++) dat[br] ^= (1 << i);
    }

void flip(int index) {
        dat[index / B] ^= ( u32(1) << (index % B) );
    }
};
```

**预处理每个块**，每个块对应$$[0, mask]$$区间内的所有值，可以打表处理
每个值它们的**前缀 0/1 个数，后缀 0/1 个数，中间的 0/1 个数**
> 值得注意的是，有时候给出的询问是有多少个全 0 子区间，那么当你求出**极长全 0 段**（长度是$$len$$）之后
答案需要立刻统计，$$mid(x) \leftarrow f(len) = len + \binom{len}{2}$$
有时候还需要单独维护一个`mid`信息，很多时候 mid 有关的值，因为它是一整个完整的段，可以被直接计算

```bash
// leading 0, tail 0, mid 0
vector<i64> L(1<<B, 0), R(1<<B, 0), mid(1<<B, 0);

void calc() {
    // 每一段，总共出现的数就只有 [0...MASK]，先打表
    for (int x = 0; x <= MASK; x++) {
        i64 cnt = 0;
        bool fst = true;

for (int i = 0; i < B; i++) {
            if ( !(x >> i & 1) ) cnt++;
            else {
                if (fst) { fst = false, L[x] = cnt; }
                else mid[x] += 1LL * cnt * (cnt + 1) / 2;

cnt = 0;
            }
            R[x] = cnt;
            // 如果是全 0 段，统计在后缀中，前缀 L[x] = 0
        }
    }
}
```

**块和块的合并**
```bash
i64 check(const Bitset &lhs, const Bitset &rhs, int len) {
    int bn = len / B, bit = len % B;

i64 cnt = 0, res = 0;
    // cnt0 记录段内的 0，res 记录全部的 0

for (int i = 0; i < bn; i++) {
        int x = lhs.dat[i] ^ rhs.dat[i];

if (x == 0) cnt += B;
        else {
            cnt += L[x], res += mid[x] + 1LL * cnt * (cnt + 1) / 2;
            cnt = R[x];

// cnt = R[x]，为下一段的合并做准备
        }
    }

int x = lhs.dat[bn] ^ rhs.dat[bn];
    for (int i = 0; i < bit; i++) {
        if ( !(x >> i & 1) ) cnt++;
        else {
            res += 1LL * cnt * (cnt + 1) / 2, cnt = 0;
        }
    }
    res += cnt * (cnt + 1) / 2;
    return res;
}
```

## 2025牛客暑期多校训练营1
**[H.Symmetry Intervals 2](https://ac.nowcoder.com/acm/contest/108298/H)**
给定二进制串`S`，`q`个询问，两种操作
第一种，给定两个数`l, r`，**翻转**区间`[l, r]`
第二种，给定`l, a, b`，问有多少个区间$$[u, v]$$满足，对于所有$$x \in [u, v]$$
满足`S[a+x-1] = S[b+x-1]`成立

**算法分析**
第二种询问，就是对`lhs = [a, a+l-1],  rhs = [b, b+l-1]`**切片**，然后统计切片中，极长连续的全`0`段的长度

比如算出来是$$cnt$$，那么对答案的贡献就是$$\displaystyle cnt + \binom{cnt}{2} = \dfrac{cnt(cnt+1)}{2}$$

> 接下来考虑如何实现？

对于操作1，因为翻转操作，区间异或，是支持差分的，只需要**单点修改**，$$S(l) \oplus 1, S(r+1) \oplus 1$$
但是位分块操作，支持**区间翻转**

实际上，对于第一种操作，我们只要把操作序列的`pos`全部都缓存下来，因为$$\oplus 1$$操作，没有区别

遇到第二种操作的时候，先对**缓存的操作序列排序**，对于$$[pos\_{i}, pos\_{i+1}-1]$$
（当然要满足$$pos\_{i} < pos\_{i+1}$$）
在**位分块**上，执行区间翻转

然后对`lhs = [a, a+l-1], rhs = [b, b+l-1]`执行**区间切片**，看一下$$lhs \oplus rhs$$有多少个全`0`的子段

对于$$lhs \oplus rhs$$**每个块合并**，统计出**极长全 0 子段**，将$$\dfrac{cnt(cnt + 1)}{2}$$加入答案中即可

看完文章有啥想法

算法小站

wiki 主题

数据结构

位分块

目录