君君算法课堂-数列分块
目录
- 数列分块
- 区间加法，单点查值
- 区间加法，区间询问小于 的元素个数
- 区间加法，查询区间对于 的前驱
- 区间加法，区间求和
- 区间乘法，区间加法，单点询问
- 问题总结
数列分块
当处理数列问题时，有时会遇到区间修改或区间询问操作
使用暴力方法无疑会在 区间 上耗时较多
而对于和区间有关的问题，常常通过维护区间信息等来实现
分块，即将序列分成一小块一小块来进行处理维护
将每一块当作一个整体，记录维护整体的有关信息，来减小时间复杂度
在对序列进行分块时，有 序列总长度 = 每一块序列长度 * 块数
维护序列信息时，当区间长度够长时，维护信息的复杂度与块数有关
但又由于所询问的区间不能够将序列块刚好完整覆盖
则对于 残块 来说，维护信息的复杂度与每一块序列的长度有关
因此，一般我们分块时，将每块序列长度分为 \(\sqrt{n}\)，块数 也在 \(\sqrt{n}\) 的级别
这样能够有效降低时间复杂度
下面通过几道例题来理解分块的操作
区间加法，单点查值
题目链接：6277. 数列分块入门 1
令 \(len = \sqrt{n}\) 记录每一块的序列长度，\(pos[i]\) 记录 \(a[i]\) 所属于的块的 编号
\(L[i]\) 记录 第 \(i\) 个块 的左边界下标，\(R[i]\) 记录 第 \(i\) 个块 的右边界下标（\([L_i, R_i]\)）
\(tag[i]\) 记录 编号为 \(i\) 的块 所维护的区间和信息
对于区间加法（区间 \([l,r]\) 加 \(c\)）的操作，分情况讨论
若区间仅覆盖一个块，则暴力修改即可
即若 \(pos[l] = pos[r]\)：暴力修改每个单点的值
否则执行以下操作：
- 区间左端点 到 其所对应块的右端点：暴力修改
- 区间右端点 到 其所对应块的左端点：暴力修改
- 其它被询问区间完整覆盖的块：维护区间信息即可
对于单点询问，输出 单点的值及该点所在块维护信息 的和即可
时间复杂度：单次区间询问 \(O(\sqrt{n})\)，单点查询 \(O(1)\)
#include
#include
#include
using namespace std;
const int N = 1e5 + 5;
int n, len, pos[N], L[N], R[N], a[N], tag[N];
void change(int l, int r, int c) {
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) a[i] += c;
return;
}
for(int i = l; i <= R[pos[l]]; i ++) a[i] += c;
for(int i = L[pos[r]]; i <= r; i ++) a[i] += c;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) tag[i] += c;
}
int main() {
scanf("%d", &n); len = sqrt(n);
for(int i = 1; i <= n; i ++) cin >> a[i], pos[i] = (i-1) / len + 1;
for(int i = 1; i <= pos[n]; i ++) L[i] = (i-1)*len + 1, R[i] = min(len * i, n);
for(int i = 1, opt, l, r, c; i <= n; i ++) {
scanf("%d%d%d%d", &opt, &l, &r, &c);
if(opt == 0) change(l, r, c);
if(opt == 1) printf("%d\n", a[r] + tag[pos[r]]);
}
return 0;
}
区间加法，区间询问小于 \(x\) 的元素个数
题目链接：6278. 数列分块入门 2
首先进行数列分块，考虑如何对信息进行维护
需要方便求出 某段区间 内小于 \(x\) 的元素个数
考虑如下做法：
对于原数列 \(a[n]\)，建立新数组 \(b[i]\)，其中在每块内 \(b[i]\) 有序
在询问时便能较为方便的求出 区间内小于 \(x\) 的元素个数
对于区间加法，同之前的方法，不过需要在维护 \(a[i]\) 的同时维护 \(b[i]\)
保证每个块内 \(b[i]\) 有序
在查询时统计每个块内的答案再求和即可
注：\(lower\_bound\) 查找 \(≥x\) 的元素中最小的一个（序列需先排好序），并返回指向该元素的迭代器
#include
#include
#include
#include
using namespace std;
const int N = 5e5 + 5;
int n, len, a[N], b[N], pos[N], L[N], R[N], tag[N];
void change(int l, int r, int c) {
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) a[i] += c;
for(int i = L[pos[l]]; i <= R[pos[r]]; i ++) b[i] = a[i];
sort(b + L[pos[l]], b + R[pos[l]] + 1);
return;
}
for(int i = l; i <= R[pos[l]]; i ++) a[i] += c;
for(int i = L[pos[r]]; i <= r; i ++) a[i] += c;
for(int i = L[pos[l]]; i <= R[pos[l]]; i ++) b[i] = a[i];
for(int i = L[pos[r]]; i <= R[pos[r]]; i ++) b[i] = a[i];
sort(b + L[pos[l]], b + R[pos[l]] + 1);
sort(b + L[pos[r]], b + R[pos[r]] + 1);
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) tag[i] += c;
}
int query(int l, int r, int c) {
int res = 0;
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) {
if(a[i] + tag[pos[i]] < c) res ++;
}
return res;
}
for(int i = l; i <= R[pos[l]]; i ++) if(a[i] + tag[pos[l]] < c) res ++;
for(int i = L[pos[r]]; i <= r; i ++) if(a[i] + tag[pos[r]] < c) res ++;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) {
int p = lower_bound(b + L[i], b + R[i] + 1, c - tag[i]) - b - 1;
res += max(p - L[i] + 1, 0);
}
return res;
}
int main() {
cin >> n; len = sqrt(n);
for(int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i];
for(int i = 1; i <= n; i ++) pos[i] = (i-1) / len + 1;
for(int i = 1; i <= pos[n]; i ++)
L[i] = (i-1) * len + 1, R[i] = min(i * len, n), sort(b + L[i], b + R[i] + 1);
for(int i = 1, opt, l, r, c; i <= n; i ++) {
cin >> opt >> l >> r >> c;
if(opt == 0) change(l, r, c);
if(opt == 1) cout << query(l, r, c * c) << "\n";
}
return 0;
}
区间加法，查询区间对于 \(x\) 的前驱
题目链接：6279. 数列分块入门 3
方法类似第二题，只不过在求解时，返回小于 \(x\) 的数的最大值即可
#include
#include
#include
#include
using namespace std;
const int N = 5e5;
int n, len, tot, a[N], b[N], pos[N], L[N], R[N], tag[N];
void change(int l, int r, int c) {
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) a[i] += c;
for(int i = L[pos[l]]; i <= R[pos[r]]; i ++) b[i] = a[i];
sort(b + L[pos[l]], b + R[pos[r]] + 1);
return;
}
for(int i = l; i <= R[pos[l]]; i ++) a[i] += c;
for(int i = L[pos[r]]; i <= r; i ++) a[i] += c;
for(int i = L[pos[l]]; i <= R[pos[l]]; i ++) b[i] = a[i];
for(int i = L[pos[r]]; i <= R[pos[r]]; i ++) b[i] = a[i];
sort(b + L[pos[l]], b + R[pos[l]] + 1);
sort(b + L[pos[r]], b + R[pos[r]] + 1);
for(int i = pos[l] + 1; i <= pos[r]-1; i ++) tag[i] += c;
}
int query(int l, int r, int c) {
int ans = -1;
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) {
if(a[i] + tag[pos[i]] < c)
ans = max(ans, a[i]+tag[pos[i]]);
}
return ans;
}
for(int i = l; i <= R[pos[l]]; i ++) {
if(a[i] + tag[pos[l]] < c)
ans = max(ans, a[i] + tag[pos[l]]);
}
for(int i = L[pos[r]]; i <= r; i ++) {
if(a[i] + tag[pos[r]] < c)
ans = max(ans, a[i] + tag[pos[r]]);
}
for(int i = pos[l] + 1; i <= pos[r]-1; i ++) {
int p = lower_bound(b + L[i], b + R[i] + 1, c - tag[i]) - b - 1;
if(p < L[i]) continue;
ans = max(ans, b[p] + tag[i]);
}
return ans;
}
int main() {
cin >> n; len = sqrt(n);
for(int i = 1; i <= n; i ++) cin >> a[i], pos[i] = (i-1)/len + 1, b[i] = a[i];
for(int i = 1; (i-1) * len <= n; i ++)
L[i] = (i-1)*len+1, R[i] = min(n, i*len), sort(b+L[i], b+R[i]+1);
tot = pos[n];
for(int i = 1, opt, l, r, c; i <= n; i ++) {
cin >> opt >> l >> r >> c;
if(opt == 0) change(l, r, c);
if(opt == 1) cout << query(l, r, c) << endl;
}
return 0;
}
区间加法，区间求和
题目链接：6280. 数列分块入门 4
用 \(sum[i]\) 来维护第 \(i\) 个块 的区间和，\(tag[i]\) 维护单点 \(a[x]\)（属于块 \(i\)） 未能加和的值（懒标记）
\(tag[i]\) 能够便于统计残块信息，对于整个块，通过一个标记信息来维护区间信息
这种思想在一些数据结构中很常见，能够极大提高程序运行效率
#include
#include
#include
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, len, a[N], pos[N], L[N], R[N], tag[N], sum[N];
void change(int l, int r, int c) {
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) a[i] += c;
sum[pos[l]] += (r - l + 1) * c;
return;
}
for(int i = l; i<= R[pos[l]]; i ++) a[i] += c;
sum[pos[l]] += (R[pos[l]] - l + 1) * c;
for(int i = L[pos[r]]; i <= r; i ++) a[i] += c;
sum[pos[r]] += (r - L[pos[r]] + 1) * c;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) tag[i] += c, sum[i] += len * c;
}
int query(int l, int r, int c) {
int res = 0;
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) {
(res += a[i] + tag[pos[i]]) %= c;
}
return res;
}
for(int i = l; i <= R[pos[l]]; i ++) (res += a[i] + tag[pos[l]]) %= c;
for(int i = L[pos[r]]; i <= r; i ++) (res += a[i] + tag[pos[r]]) %= c;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) (res += sum[i]) %= c;
return res;
}
signed main() {
cin >> n; len = sqrt(n);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) pos[i] = (i-1) / len + 1, sum[pos[i]] += a[i];
for(int i = 1; i <= pos[n]; i ++)
L[i] = (i-1) * len + 1, R[i] = min(i * len, n);
for(int i = 1, opt, l, r, c; i <= n; i ++) {
cin >> opt >> l >> r >> c;
if(opt == 0) change(l, r, c);
if(opt == 1) cout << query(l, r, c + 1) << "\n";
}
return 0;
}
区间乘法，区间加法，单点询问
题目链接：6283. 数列分块入门 7
对于每个块，维护一个乘法标记 \(mul[i]\) 和一个加法标记 \(add[i]\)
对于每次修改操作，将操作区间两端的标记影响进行消除
（消除标记时，先消除乘法标记，再消除加法标记）
考虑对于中间的块
进行加法操作时，之前的乘法标记不会影响到目前的操作
而进行乘法操作时，之前的加法标记却会影响到当前的操作
需要将加法标记也进行变化，来正确维护标记
#include
#include
#include
using namespace std;
const int N = 1e5 + 5, mod = 1e4 + 7;
int n, len, a[N], pos[N], L[N], R[N], add[N], mul[N];
void reset(int x) {
for(int i = L[x]; i <= R[x]; i ++) {
(a[i] = a[i] * mul[x] + add[x]) %= mod;
}
add[x] = 0; mul[x] = 1;
}
void change_add(int l, int r, int c) {
reset(pos[l]);
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) (a[i] += c) %= mod;
return;
}
reset(pos[r]);
for(int i = l; i <= R[pos[l]]; i ++) (a[i] += c) %= mod;
for(int i = L[pos[r]]; i <= r; i ++) (a[i] += c) %= mod;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++) (add[i] += c) %= mod;
}
void change_mul(int l, int r, int c) {
reset(pos[l]);
if(pos[l] == pos[r]) {
for(int i = l; i <= r; i ++) (a[i] *= c) %= mod;
return;
}
reset(pos[r]);
for(int i = l; i <= R[pos[l]]; i ++) (a[i] *= c) %= mod;
for(int i = L[pos[r]]; i <= r; i ++) (a[i] *= c) %= mod;
for(int i = pos[l] + 1; i <= pos[r] - 1; i ++)
(mul[i] *= c) %= mod, (add[i] *= c) %= mod;
}
int main() {
cin >> n; len = sqrt(n);
for(int i = 1; i <= n; i ++) cin >> a[i], pos[i] = (i-1) / len + 1;
for(int i = 1; i <= pos[n]; i ++) L[i] = (i-1) * len + 1, R[i] = min(len * i, n);
for(int i = 1; i <= pos[n]; i ++) mul[i] = 1;
for(int i = 1, opt, l, r, c; i <= n; i ++) {
cin >> opt >> l >> r >> c;
if(opt == 0) change_add(l, r, c);
if(opt == 1) change_mul(l, r, c);
if(opt == 2) cout << ((a[r] * mul[pos[r]] + add[pos[r]]) % mod) << "\n";
}
return 0;
}
问题总结
对于区间上的操作，能够通过将区间拆分，统计区间所维护的信息
即使方法可能会有些暴力，但由于 每个块的大小 并不大
因此总的复杂度并不会太高
能够帮助我们解决一些较为复杂的问题
分块的特点就在于方法虽然暴力，但是容易实现
可以避免使用其他复杂的数据结构（难以调试）
便可以成功求解问题
对于分块解决问题，主要考虑对于区间信息的维护
即如何通过一种效率合适的方法将问题的答案进行统计