问题描述：

[TOC]

分块

维护常见的区间操作与查询操作。

将数列分成$\sqrt n$块，每块有$\sqrt n$ 个数字。

核心为：快速维护整块的操作，暴力维护非整块的操作。

要考虑的有三个：

1、不完整的块如何处理

2、完整的块如何处理

3、需要预处理什么信息

数列分块入门1

区间加、单点查询

区间修改：区间内每个数字都加v

单点查询：

整块的：直接累计lazy[i]

非整块的，最多有两个非整块的，直接暴力即可。

int n, a[N]; int len, tot, id[N], lazy[N]; void build() { len = sqrt(n); //块的长度 tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) id[i] = (i - 1) / len + 1; } void add(int l, int r, ll x) { // 区间加法 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) a[i] += x; return; } for (int i = l; id[i] == sid; i++) a[i] += x; for (int i = sid + 1; i < eid; i++) lazy[i] += x; // 更新区间和数组(完整的块) for (int i = r; id[i] == eid; i--) a[i] += x; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, x; cin >> op >> l >> r >> x; if (op == 0) add(l, r, x); else cout << a[r] + lazy[id[r]] << endl; } return 0; }

数列分块入门4

区间加、区间和

区间修改：区间每个数字都加v

区间查询：区间和

修改和之前一样

查询类似于修改，整块直接求和，非整块暴力求和。

int id[N] , n , len; // id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优 ll a[N], lazy[N], s[N]; // a 数组表示数据数组, lazy 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s表示块内元素总和 void build() { len = sqrt(n); for (int i = 1; i <= n; i++) { id[i] = (i - 1) / len + 1; s[id[i]] += a[i]; } } void add(int l, int r, ll x) { // 区间加法 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) a[i] += x, s[sid] += x; return; } for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x; for (int i = sid + 1; i < eid; i++) lazy[i] += x, s[i] += len * x; // 更新区间和数组(完整的块) for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x; // 以上两行不完整的块直接简单求和,就OK } ll query(int l, int r, ll p) { // 区间查询 int sid = id[l], eid = id[r]; ll ans = 0; if (sid == eid) { // 在一个块里直接暴力求和 for (int i = l; i <= r; i++) ans = (ans + a[i] + lazy[sid]) % p; return ans; } for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + lazy[sid]) % p; for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p; for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + lazy[eid]) % p; // 和上面的区间修改是一个道理 return ans; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) add(l, r, c); else cout << query(l, r, c + 1) << endl; } return 0; }

数列分块入门7

区间加、区间乘、单点查询

区间修改：区间乘法 / 区间加法

单点查询

我们考虑用两个标记，乘法标记 加法标记

令 乘法标记 的优先级高于 加法标记 （如果反过来的话，新的加法标记无法处理）

若当前的一个块乘以 m_1 后加上 a_1，这时进行一个乘 m_2 的操作，则原来的标记变成 (m_1 m_2, a_1 m_2)

若当前的一个块乘以 m_1 后加上 a_1，这时进行一个加 a_2 的操作，则原来的标记变成 (m_1, a_1 + a_2)

int n, q, tot; int id[M], len, L[M], R[M]; ll a[M], mul[M], add[M]; void build() { len = sqrt(n); //块的长度 tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) id[i] = (i - 1) / len + 1; for (int i = 1; i <= tot; i++) { //记录每一块的起点和终点 L[i] = (i - 1) * len + 1; R[i] = i * len; mul[i] = 1; } R[tot] = n; //最后一块不一定有len个，末尾是n } void pushdown(int ID) { //乘法标记的优先级高于加法（如果反过来的话，新的加法标记无法处理) for (int i = L[ID]; i <= R[ID]; i++) a[i] = (a[i] * mul[ID] % mod + add[ID]) % mod; mul[ID] = 1; add[ID] = 0; } void update_add(int l, int r, ll x) { // 区间加法 (mul,add+x) int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 pushdown(sid); for (int i = l; i <= r; i++) a[i] = (a[i] + x) % mod; return; } pushdown(sid); pushdown(eid); for (int i = l; i <= R[sid]; i++) a[i] = (a[i] + x) % mod; for (int i = sid + 1; i < eid; i++) add[i] = (add[i] + x) % mod; for (int i = L[eid]; i <= r; i++) a[i] = (a[i] + x) % mod; } void update_mul(int l, int r, ll x) { // 区间乘法 (mul*x,add+x) int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 pushdown(sid); for (int i = l; i <= r; i++) a[i] = (a[i] * x) % mod; return; } pushdown(sid); pushdown(eid); for (int i = l; i <= R[sid]; i++) a[i] = a[i] * x % mod; for (int i = sid + 1; i < eid; i++) add[i] = add[i] * x % mod, mul[i] = mul[i] * x % mod; for (int i = L[eid]; i <= r; i++) a[i] = a[i] * x % mod; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) update_add(l, r, c); else if (op == 1) update_mul(l, r, c); else cout << (a[r] * mul[id[r]] % mod + add[id[r]]) % mod << endl; } return 0; }

数列分块入门2

区间加、区间查询小于x的数字个数

区间修改：区间每个数字都加v

区间查询：区间内小于x的数字个数

考虑每一块内都是有序的。

整块修改：直接加就行，不会影响有序性

非整块修改：暴力加，然后重新排序。

整块查询：二分

非整块查询：暴力即可

int n, q, tot; int id[M], len, L[M], R[M]; ll a[M], lazy[M], t[M]; void Sort(int ID) { for (int i = L[ID]; i <= R[ID]; i++) t[i] = a[i]; sort(t + L[ID], t + R[ID] + 1); } void build() { len = sqrt(n); //块的长度 tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) id[i] = (i - 1) / len + 1; for (int i = 1; i <= tot; i++) { //记录每一块的起点和终点 L[i] = (i - 1) * len + 1; R[i] = i * len; } R[tot] = n; //最后一块不一定有len个，末尾是n for (int i = 1; i <= tot; i++) Sort(i); //块内排序 } void add(int l, int r, ll x) { // 区间加法 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) a[i] += x; Sort(sid); return; } for (int i = l; i <= R[sid]; i++) a[i] += x; for (int i = sid + 1; i < eid; i++) lazy[i] += x; for (int i = L[eid]; i <= r; i++) a[i] += x; Sort(sid); Sort(eid); } ll query(int l, int r, int x) { // 区间查询 int ans = 0, sid = id[l], eid = id[r]; if (sid == eid) { for (int i = l; i <= r; i++) if (a[i] + lazy[sid] < x) ans++; return ans; } for (int i = l; i <= R[sid]; i++) if (a[i] + lazy[sid] < x) ans++; for (int i = sid + 1; i < eid; i++) ans = ans + (lower_bound(t + L[i], t + R[i] + 1, x - lazy[i]) - t) - L[i]; for (int i = L[eid]; i <= r; i++) if (a[i] + lazy[eid] < x) ans++; return ans; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) add(l, r, c); else cout << query(l, r, c * c) << endl; } return 0; }

数列分块入门3

区间加、区间查询x的前驱

区间修改：区间每个数字都加v

区间查询：区间内x的前驱，也就是区间内小于x的最大的数字。

这个题做法可以和上一个题一样即可，只需要稍微改改二分的过程。

int n, q, tot; int id[M], len, L[M], R[M]; ll a[M], lazy[M], t[M]; void Sort(int ID) { for (int i = L[ID]; i <= R[ID]; i++) t[i] = a[i]; sort(t + L[ID], t + R[ID] + 1); } void build() { len = sqrt(n); //块的长度 tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) id[i] = (i - 1) / len + 1; for (int i = 1; i <= tot; i++) { //记录每一块的起点和终点 L[i] = (i - 1) * len + 1; R[i] = i * len; } R[tot] = n; //最后一块不一定有len个，末尾是n for (int i = 1; i <= tot; i++) Sort(i); //块内排序 } void add(int l, int r, ll x) { // 区间加法 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) a[i] += x; Sort(sid); return; } for (int i = l; i <= R[sid]; i++) a[i] += x; for (int i = sid + 1; i < eid; i++) lazy[i] += x; for (int i = L[eid]; i <= r; i++) a[i] += x; Sort(sid); Sort(eid); } ll query(int l, int r, int x) { // 区间查询 ll ans = -1; int sid = id[l], eid = id[r]; if (sid == eid) { for (int i = l; i <= r; i++) if (a[i] + lazy[sid] < x) ans = max(ans, a[i] + lazy[sid]); return ans; } for (int i = l; i <= R[sid]; i++) if (a[i] + lazy[sid] < x) ans = max(ans, a[i] + lazy[sid]); for (int i = sid + 1; i < eid; i++) { int pos = (lower_bound(t + L[i], t + R[i] + 1, x - lazy[i]) - t); if (--pos < L[i]) continue; ans = max(ans, t[pos] + lazy[i]); } for (int i = L[eid]; i <= r; i++) if (a[i] + lazy[eid] < x) ans = max(ans, a[i] + lazy[eid]); return ans; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) //修改 add(l, r, c); else cout << query(l, r, c) << endl; } return 0; }

启发：可以在整块的维护部分，用其他数据结构维护，如STL的set / multiset ，这样可以很方便的维护插入、删除元素，且代码会更短

数列分块入门5

区间开方、区间求和

区间修改：区间每个数字都开方（下取整）

区间查询：区间求和

类似于势能线段树。

一个数字经过若干次开方之后，会变成1。且次数不会很多。

所以我们考虑，维护整块：这一块内所有数字是否都已经变成0或1了。

整块修改：如果块内存在大于1的数字，那么暴力开方，如果都是0或1，则不需要动

非整块修改：暴力即可。

int id[N], n, len; // id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优 int a[N], lazy[N], s[N], L[N], R[N], tot; // a 数组表示数据数组, lazy 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s表示块内元素总和 void build() { len = sqrt(n); //块的长度 tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) { id[i] = (i - 1) / len + 1; s[id[i]] += a[i]; } for (int i = 1; i <= tot; i++) { //记录每一块的起点和终点 L[i] = (i - 1) * len + 1; R[i] = i * len; } R[tot] = n; //最后一块不一定有len个，末尾是n } void update(int l, int r, int x) { // 区间开根号，一个数字多次开根号，很快就会变为0/1 int sid = id[l], eid = id[r]; if (sid == eid) { // 在一个块中 for (int i = l; i <= r; i++) { s[sid] -= (a[i] - sqrt(a[i])); a[i] = sqrt(a[i]); } return; } for (int i = l; id[i] == sid; i++) { s[sid] -= (a[i] - sqrt(a[i])); a[i] = sqrt(a[i]); } for (int i = sid + 1; i < eid; i++) { if (lazy[i] == 1) continue; //如果这一块全是0/1，可以直接跳过 int cnt = 0; for (int j = L[i]; j <= R[i]; j++) { s[i] -= (a[j] - sqrt(a[j])); a[j] = sqrt(a[j]); if (a[j] <= 1) cnt++; } if (cnt == R[i] - L[i] + 1) lazy[i] = 1; } for (int i = r; id[i] == eid; i--) { s[eid] -= (a[i] - sqrt(a[i])); a[i] = sqrt(a[i]); } } ll query(int l, int r) { // 区间查询 int sid = id[l], eid = id[r]; ll ans = 0; if (sid == eid) { // 在一个块里直接暴力求和 for (int i = l; i <= r; i++) ans = (ans + a[i]); return ans; } for (int i = l; id[i] == sid; i++) ans = (ans + a[i]); for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]); for (int i = r; id[i] == eid; i--) ans = (ans + a[i]); return ans; } int main() { // CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) update(l, r, c); else cout << query(l, r) << endl; } return 0; }

数列分块入门8

区间修改为c，区间查询等于c的数字个数

区间修改比较简单

麻烦在区间查询比较奇怪，因为权值种类比较多， 好在要求对于[l,r]查询之后，还要将区间都修改为c。

所以我们会发现：经过几轮查询/修改之后，可能就只剩下几段不同的区间了，类似于上一个开根号的题。

所以我们考虑：维护一个块内，是否只有一种数字。

数列分块入门6

单点插入、单点查询

单点插入：在第x个数字之前插入一个数字v

单点查询：查询第x个数字是多少

注意：数据随机生成。

每一块用一个vector维护。

插入操作：先整块遍历，找到要插入到第几块中，然后直接insert即可。

查询：先整块遍历，找到查询的数字在第几块中，然后直接输出即可。

int a[N], n, len, tot; vector<int> ve[N]; void build() { len = sqrt(n); tot = n / len; //一共有多少块 if (n % len) tot++; for (int i = 1; i <= n; i++) ve[(i - 1) / len + 1].push_back(a[i]); } void update(int p, int c) { for (int i = 1; i <= tot; i++) { if (ve[i].size() < p) { p -= ve[i].size(); continue; } ve[i].insert(ve[i].begin() + p - 1, c); break; } } int query(int p) { int ans; for (int i = 1; i <= tot; i++) { if (ve[i].size() < p) { p -= ve[i].size(); continue; } ans = ve[i][p - 1]; break; } return ans; } int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(); for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) update(l, r); else cout << query(r) << endl; } return 0; }

用vector可以水很多分，N开2e5能水70分，N开1e5+5 能水过。

vector<int> ve(N); int n; int main() { CLOSE cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; ve[i] = x; } for (int i = 1; i <= n; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) ve.insert(ve.begin() + l, r); else cout << ve[r] << endl; } return 0; }

ps：如果数据不随机呢？

如果在同一块内，进行大量的单点插入，那么这个块的大小就会非常大，那么这一块的暴力就没法保证时间复杂度了。

那么可以怎么办呢？

重构，重新分块即可。

每经过$\sqrt n$ 次插入操作之后，进行一次重新分块。这样可以保证每块的大小比较均匀

int n, a[N], op, l, r, c, len, tot, cnt; vector<int> ve[N]; void build() { int cnt = 0; for (int i = 1; i <= tot; ++i) { for (int j = 0; j < ve[i].size(); ++j) a[++cnt] = ve[i][j]; //最开始ve是空的不会执行 ve[i].clear(); } len = sqrt(n); tot = n / len; if (n % len) ++tot; for (int i = 1; i <= n; ++i) ve[(i - 1) / len + 1].push_back(a[i]); } void update(int p, int c) { for (int i = 1; i <= tot; ++i) { if (ve[i].size() < p) { p -= ve[i].size(); continue; } ve[i].insert(ve[i].begin() + p - 1, c); break; } } int query(int p) { for (int i = 1; i <= tot; ++i) { if (ve[i].size() < p) { p -= ve[i].size(); continue; } return ve[i][p - 1]; } } int main() { CLOSE cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; build(); int m = n; for (int i = 1; i <= m; ++i) { cin >> op >> l >> r >> c; if (op == 0) { ++n; if (cnt >= (int)sqrt(n)) { cnt = 0; build(); } update(l, r); ++cnt; } else cout << query(r) << endl; } return 0; } 网友解答：

---

--【壹】--：

好呢好呢，最近几天更新出来sticker14.b3a3c84.png196×196 10.2 KB

---

--【贰】--：

大佬厉害。想知道，大佬可以多谢谢线段树的知识点吗？最近才了解到这个数据结构的强大（我确实是了解的太晚了）。