我的算法书 - Argestes and Sequence

这两个题目（HDU 5057）是一个经典的带修改区间查询问题。我们需要在一个数组上进行单点修改，并查询一个区间内有多少个数字的第 $D$ 位是 $P$ 。

由于数据范围 $N, M \le 10^5$ 且有多组测试数据，我们需要一个高效的解法。暴力做法 $O(M \times N)$ 肯定会超时。你提到的**分块（Square Root Decomposition）和树状数组（Binary Indexed Tree, BIT）**都是解决这类问题的常用方法。

下面我将分别详细介绍这两种方法，并提供带有快读优化的 C++ 代码。

预备知识：如何获取数字的第 D 位

题目中规定第 1 位是最低位（个位）。数字 $V$ 的第 $D$ 位可以通过以下公式计算： $(V / 10^{D-1}) \% 10$

由于 $D$ 最大为 10，我们可以预处理 $10$ 的幂次来加速计算。

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11

        long long powers[11];
void precompute_powers() {
    powers[1] = 1;
    for (int i = 2; i <= 10; ++i) powers[i] = powers[i - 1] * 10;
}

// 获取 val 的第 D 位数字
inline int get_digit(long long val, int D) {
    return (val / powers[D]) % 10;
}

方法一：树状数组 (BIT)

树状数组擅长处理单点修改和区间前缀和查询。这里的查询条件是“第 $D$ 位是 $P$ ”，这并不是一个直接的数值求和。

核心思想： 我们可以建立多个树状数组。具体来说，对于每一个可能的位数 $D$ ( $1 \le D \le 10$ ) 和每一个可能的数字 $P$ ( $0 \le P \le 9$ )，我们都建立一个树状数组。记 tree[D][P] 为一个树状数组。如果原数组 $a[i]$ 的第 $D$ 位是 $P$ ，那么我们在 tree[D][P] 的位置 $i$ 上加上 1。

这样，查询区间 $[L, R]$ 内第 $D$ 位是 $P$ 的数字个数，就转化为了在 tree[D][P] 上查询区间 $[L, R]$ 的和，即 query(tree[D][P], R) - query(tree[D][P], L-1)。

复杂度分析：

空间复杂度：我们需要 $10 \times 10 = 100$ 个大小为 $N$ 的树状数组。总空间约为 $100 \times 10^5 \times 4$ 字节 $\approx 40$ MB，是可以接受的。
时间复杂度：
- 初始化：遍历 $N$ 个数，对每个数更新 10 个 BIT，总共 $O(N \log N \times 10)$ 。
- 修改 (S X Y)：修改一个数涉及到在 10 个 BIT 中减去旧值的贡献，并加上新值的贡献。总共 $O(\log N \times 20)$ 。
- 查询 (Q L R D P)：只需要在指定的一个 BIT 上进行两次查询。总共 $O(\log N)$ 。
- 总时间复杂度为 $O((N + M) \log N)$ ，常数较大但足以通过。

特征数组思想

你的理解非常准确，完全正确！

这正是这个解法的核心思想。你已经抓住了问题的本质。

让我用更正式一点的语言把你的想法再梳理一遍，加深印象：

1. 核心思想：特征数组 (Indicator Array)

你提到的“桶”或者那个 [1 1 1 0 0 0] 的数组，在算法中通常被称为特征数组或者指示器数组。

对于题目中的每一个特定的查询要求——“第 $D$ 位是 $P$ ”，我们可以想象存在一个概念上的布尔数组（只包含 0 和 1），记作 $B_{D,P}$ 。

数组 $B_{D,P}$ 的定义如下：对于原数组 $a$ 中的第 $i$ 个元素 $a[i]$ ：

如果 $a[i]$ 的第 $D$ 位恰好是 $P$ ，那么 $B_{D,P}[i] = 1$ 。
如果 $a[i]$ 的第 $D$ 位不是 $P$ ，那么 $B_{D,P}[i] = 0$ 。

举个例子： 假设原数组 $a = [123, 456, 128, 789, 421]$ 我们关注：第 2 位（十位）是 2 的数字。即 $D=2, P=2$ 。

$a[1]=1\textbf{2}3 \rightarrow$ 符合 $\rightarrow B_{2,2}[1] = 1$
$a[2]=456 \rightarrow$ 不符 $\rightarrow B_{2,2}[2] = 0$
$a[3]=1\textbf{2}8 \rightarrow$ 符合 $\rightarrow B_{2,2}[3] = 1$
$a[4]=789 \rightarrow$ 不符 $\rightarrow B_{2,2}[4] = 0$
$a[5]=4\textbf{2}1 \rightarrow$ 符合 $\rightarrow B_{2,2}[5] = 1$

那么，概念上的特征数组 $B_{2,2}$ 就是 [1, 0, 1, 0, 1]。

2. 问题的转化

题目要求查询：在区间 $[L, R]$ 内，有多少个数字满足“第 $D$ 位是 $P$ ”。

转化到特征数组 $B_{D,P}$ 上，这个问题就变成了： 求特征数组 $B_{D,P}$ 在区间 $[L, R]$ 内的元素和。

即： $\sum_{i=L}^{R} B_{D,P}[i]$ 。

因为满足条件的记为 1，不满足的记为 0，所以它们的和就是满足条件的个数。

3. BIT 的角色：动态维护区间和

现在问题变成了我们最熟悉的形式：单点修改，区间求和。

如果数组 $B_{D,P}$ 是静态不变的，我们可以用前缀和数组在 $O(1)$ 时间内求出区间和。

但题目有修改操作（S X Y）：将 $a[X]$ 改为 $Y$ 。这意味着 $a[X]$ 的各个位上的数字可能会变，从而导致多个特征数组在位置 $X$ 上的值（0 或 1）发生变化。

如果用原始数组维护 $B_{D,P}$ ，修改是 $O(1)$ ，但区间求和是 $O(N)$ ，太慢。
如果用前缀和数组维护 $B_{D,P}$ ，区间求和是 $O(1)$ ，但修改是 $O(N)$ ，太慢。

这时候，树状数组 (BIT) 就登场了。它正是为了平衡这两者而生的数据结构。

你所说的 tree[D][P]，实际上就是基于特征数组 $B_{D,P}$ 构建的树状数组。

当我们在 $a[X]$ 的第 $D$ 位上观察到数字 $P$ 时，我们在概念上把 $B_{D,P}[X]$ 设为了 1。在代码里，我们就执行 bit_update(tree[D][P], X, 1)。
当我们查询区间 $[L, R]$ 时，我们实际上是在求特征数组的区间和，代码里就是 bit_query(tree[D][P], R) - bit_query(tree[D][P], L - 1)。

总结

你的想法非常透彻。

这个解法就是把一个复杂的复合条件查询，通过特征化（变成 0/1 数组）转化为标准的区间求和问题，然后因为需要支持动态修改，所以引入了树状数组来维护这个求和过程。

C++ 代码实现 (BIT)：

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

        #include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

// --- 快读快写模板 ---
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline long long readll() {
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline void write(int x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
// --------------------

const int MAXN = 100005;
long long a[MAXN]; // 原数组
int n, m;
int tree[11][10][MAXN]; // 100个树状数组：tree[D][P][idx]
long long powers[11];   // 预存10的幂

void precompute_powers() {
    powers[1] = 1;
    for (int i = 2; i <= 10; ++i) powers[i] = powers[i - 1] * 10;
}

inline int get_digit(long long val, int D) {
    return (val / powers[D]) % 10;
}

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

// 在指定的 BIT 上进行更新
void bit_update(int d, int p, int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) {
        tree[d][p][idx] += val;
    }
}

// 在指定的 BIT 上进行前缀和查询
int bit_query(int d, int p, int idx) {
    int sum = 0;
    for (; idx > 0; idx -= lowbit(idx)) {
        sum += tree[d][p][idx];
    }
    return sum;
}

void solve() {
    n = read(); m = read();
    memset(tree, 0, sizeof(tree)); // 多组数据，切记清空
    for (int i = 1; i <= n; ++i) {
        a[i] = readll();
        // 初始化 BIT，对每个位置的每一位进行记录
        for (int d = 1; d <= 10; ++d) {
            bit_update(d, get_digit(a[i], d), i, 1);
        }
    }

    char type[2];
    for (int k = 0; k < m; ++k) {
        scanf("%s", type);
        if (type[0] == 'S') { // 修改操作
            int x = read();
            long long y = readll();
            long long old_val = a[x];
            // 1. 移除旧值的贡献
            for (int d = 1; d <= 10; ++d) {
                bit_update(d, get_digit(old_val, d), x, -1);
            }
            a[x] = y; // 更新原数组
            // 2. 添加新值的贡献
            for (int d = 1; d <= 10; ++d) {
                bit_update(d, get_digit(y, d), x, 1);
            }
        } else { // 查询操作
            int l = read(), r = read(), d = read(), p = read();
            // 利用区间减法原理查询
            int ans = bit_query(d, p, r) - bit_query(d, p, l - 1);
            write(ans);
            putchar('\n');
        }
    }
}

int main() {
    precompute_powers(); // 预处理
    int t = read();
    while (t--) {
        solve();
    }
    return 0;
}

方法二：分块 (Square Root Decomposition)

分块是一种通用性很强的方法，特别适合处理一些树状数组或线段树不好维护的复杂区间信息。

核心思想：

本质: 区间信息是什么 ask(l,r,d,p) , 可以用这个来统计区间信息,关键字d,p, $d \times p = 10 \times 10 = 100$ ,任何一个区间的信息可以使用长度为100的数组存下. 使用分块来进行暴力优化

将数组 $a$ 分成 $\sqrt{N}$ 个块，每个块的大小约为 $\sqrt{N}$ 。对于每一个块，我们维护一个统计数组 cnt[block_id][D][P]，表示在第 block_id 个块中，第 $D$ 位是 $P$ 的数字有多少个。

修改 (S X Y)：找到 $X$ 所在的块，更新该块的 cnt 数组。先减去旧值 $a[X]$ 在各个位上的计数，然后更新 $a[X]=Y$ ，再加上新值 $Y$ 在各个位上的计数。复杂度 $O(10)$ 。
查询 (Q L R D P)：查询区间 $[L, R]$ 可能跨越多个块。
- 对于两端不完整的块（散块），直接暴力遍历原数组 $a$ 进行统计。复杂度 $O(\sqrt{N})$ 。
- 对于中间完整的块，直接累加预处理好的 cnt[block_id][D][P]。复杂度 $O(\sqrt{N})$ 。

复杂度分析：

空间复杂度：cnt 数组大小约为 $\sqrt{N} \times 10 \times 10 \approx 320 \times 100 = 3.2 \times 10^4$ ，非常小。
时间复杂度：
- 初始化： $O(N \times 10)$ 。
- 修改： $O(1)$ （常数为 10）。
- 查询： $O(\sqrt{N})$ 。
- 总时间复杂度为 $O(N + M\sqrt{N})$ 。

通常来说， $O(M \log N)$ 优于 $O(M \sqrt{N})$ ，但分块算法常数较小，在这个题目中也是可以通过的。

C++ 代码实现 (分块)：

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

        #include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
typedef  long long ll;
int n,m;
ll a[maxn]; // 原数组，存储每个数字的值

long long powers[11]; // 用于存储 10 的幂次方，powers[i] = 10^(i-1)

// 预处理 10 的幂次方
void precompute_powers() {
    powers[1] = 1;
    for (int i = 2; i <= 10; ++i) powers[i] = powers[i - 1] * 10;
}

// 获取数字 val 的第 D 位数字（个位是第1位）
inline int get_digit(long long val, int D) {
    return (val / powers[D]) % 10;
}

// ---- block 分块结构体
struct Block {
    ll block; // 块的大小，通常取 sqrt(n)
    ll t; // 块的总数量
    ll pos[maxn]; // pos[i] 表示原数组第 i 个元素所属的块编号
    ll st[maxn]; // st[i] 表示第 i 个块的起始下标
    ll ed[maxn]; // ed[i] 表示第 i 个块的结束下标

    ll addflag[maxn]; // 懒标记，这个题目里暂时没用到
    // cnt[i][d][p] 表示第 i 个块中，所有数字的第 d 位上，数字 p 出现的次数
    ll cnt[2005][11][10]; 

    // 初始化分块结构
    void init(){
        memset(cnt,0,sizeof(cnt)); // 清空统计数组，因为有多组数据
        block = sqrt(n); // 计算块大小
        t = n / block; // 计算完整块的数量
        if( n % block) t++; // 如果有剩余元素，块数量加 1
        
        // 确定每个块的起始和结束下标
        for(ll i = 1;i <= t ;++i ) // i: 1->t
        {
            st[i] = (i-1) * block + 1;
            ed[i] = i * block;
        }
        ed[t] = n; // 修正最后一个块的结尾下标为 n
        
        // 确定每个元素所属的块编号
        for(ll i = 1;i <= n ;++i ) // i: 1->n
        {
            pos[i] = (i-1) / block + 1;
        }

        // 初始化 cnt 数组，统计每个块内的信息
        for(ll i = 1;i <= t ;++i ) // i: 1->t
        {
            for(ll j = st[i];j <= ed[i] ;++j ) // j: 1->n
            {
                ll num = a[j]; // 使用 long long 防止溢出
                // 遍历数字 num 的每一位，更新 cnt 数组
                for(int d = 1;d <= 10;d ++) cnt[i][d][ get_digit(num, d)]++;
            }
        }
    }

    // 单点修改操作：将 a[L] 的值修改为 val
    // 这里 R 其实没用到，因为是单点修改，调用时传入 update(x, x, y)
    void update(ll L,ll R,ll val) {
        int idx = L; // 要修改的元素的下标
        int bidx = pos[L]; // 该元素所属的块编号

        // 1. 移除旧值的贡献
        // 遍历旧值 a[idx] 的每一位，在对应的 cnt 统计中减 1
        for(int d = 1;d <= 10;d++)
            cnt[bidx][d][get_digit(a[idx], d)]--;
            
        // 2. 更新原数组
        a[idx] = val;
        
        // 3. 添加新值的贡献
        // 遍历新值 val 的每一位，在对应的 cnt 统计中加 1
        for(int d = 1;d <= 10;d++)
            cnt[bidx][d][get_digit(val, d)]++;
    }

    // 区间查询操作：查询区间 [L, R] 内，第 d 位是 val 的数字有多少个
    long long query(ll L,ll R,int d,int val) {
        long long ret = 0;
        ll p = pos[L], q = pos[R]; // 计算区间两端所属的块编号
        
        if( p == q) {
            // 情况 1：查询区间在同一个块内
            // 直接暴力遍历区间 [L, R] 进行统计
            for(ll i = L;i <= R;i++) {
                if( get_digit(a[i], d) == val)
                    ret++;
            }
        }
        else {
            // 情况 2：查询区间跨越多个块
            
            // 统计中间完整的块
            for(ll i = p+1;i<=q-1;i++) {
                ret += cnt[i][d][val]; // 直接累加预处理好的统计信息
            }
            
            // 统计左侧不完整的散块
            for(ll i = L; i <= ed[p] ;i++) {
                if( get_digit(a[i], d) == val)
                    ret++;
            }
            
            // 统计右侧不完整的散块
            for(ll i = st[q];i <= R;i++) {
                if( get_digit(a[i], d) == val)
                    ret++;
            }
        }
        return ret;
    }
} myblock;


int main () {
    // 优化 I/O 操作，提高读写速度
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    
    precompute_powers(); // 程序开始时预处理 10 的幂次方

    int T;
    std::cin >> T; // 读取测试用例数量
    while (T--) {
        std::cin >> n >> m; // 读取数组大小和操作次数
        for(int i = 1;i <= n ;++i ) std::cin >> a[i]; // 读取原数组
        
        myblock.init(); // 初始化分块结构
        
        for(int i = 1;i <= m ;++i ) // i: 1->m 处理 m 次操作
        {
            char opt;
            std::cin >> opt; // 读取操作类型
            if( opt == 'Q') { // 查询操作
                int l,r,d,p;
                std::cin >> l >> r >> d >> p; // 读取查询参数
                cout << myblock.query(l, r,d,p) << "\n"; // 输出查询结果
            }
            else { // 修改操作
                int x,y;
                std::cin >> x >> y; // 读取修改参数
                myblock.update(x,x,y); // 执行单点修改
            }
        }
    }
    
    return 0;
}

总结

树状数组做法更加巧妙，利用了问题的特性（位数和数字范围小）将问题转化为多个简单的区间求和问题，理论复杂度更优。
分块做法更加直观通用，是处理此类区间问题的“万金油”，虽然理论复杂度稍高，但常数小，实现也相对简单。

两种方法结合快读快写都能通过此题。你可以根据自己的喜好选择。

目录

预备知识：如何获取数字的第 D 位

方法一：树状数组 (BIT)

特征数组思想

1. 核心思想：特征数组 (Indicator Array)

2. 问题的转化

3. BIT 的角色：动态维护区间和

总结

方法二：分块 (Square Root Decomposition)

总结