WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
块状数组 - 数据结构
## 建立块状数组 块状数组,即把一个数组分为几个块,块内信息整体保存,若查询时遇到两边不完整的块直接暴力查询。一般情况下,块的长度为 $O(\sqrt{n})$ 。详细分析可以阅读 2017 年国家集训队论文中徐明宽的《非常规大小分块算法初探》。 下面直接给出一种建立块状数组的代码。 ```cpp num = sqrt(n); for (int i = 1; i <= num; i++) st[i] = n / num * (i - 1) + 1, ed[i] = n / num * i; ed[num] = n; for (int i = 1; i <= num; i++) { for (int j = st[i]; j <= ed[i]; j++) { belong[j] = i; } size[i] = ed[i] - st[i] + 1; } ``` 其中 `st[i] ed[i]` 为块的起点和终点, `size[i]` 为块的大小。 ## 保存与修改块内信息 ### 例题 1: [教主的魔法](https://www.luogu.com.cn/problem/P2801) 我们要询问一个块内大于等于一个数的数的个数,所以需要一个 `t` 数组对块内排序。对于整块的修改,使用类似于标记永久化的方式保存。时间复杂度 $O(n\sqrt{n}\log n)$ ```cpp void Sort(int k) { for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i]; sort(t + st[k], t + ed[k] + 1); } void Modify(int l, int r, int c) { int x = belong[l], y = belong[r]; if (x == y) { for (int i = l; i <= r; i++) a[i] += c; Sort(x); return; } for (int i = l; i <= ed[x]; i++) a[i] += c; for (int i = st[y]; i <= r; i++) a[i] += c; for (int i = x + 1; i < y; i++) dlt[i] += c; Sort(x); Sort(y); } int Answer(int l, int r, int c) { int ans = 0, x = belong[l], y = belong[r]; if (x == y) { for (int i = l; i <= r; i++) if (a[i] + dlt[x] >= c) ans++; return ans; } for (int i = l; i <= ed[x]; i++) if (a[i] + dlt[x] >= c) ans++; for (int i = st[y]; i <= r; i++) if (a[i] + dlt[y] >= c) ans++; for (int i = x + 1; i <= y - 1; i++) ans += ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, c - dlt[i]) - t) + 1; return ans; } ``` ### 例题 2:寒夜方舟 两种操作: 1. 区间 $[x,y]$ 每个数都变成 $z$ 2. 查询区间 $[x,y]$ 内小于等于 $z$ 的数的个数 用 `dlt` 保存现在块内是否被整体赋值了。用一个值表示没有。对于边角块,查询前要 `pushdown` ,把块内存的信息下放到每一个数上。赋值之后记得重新 `sort` 一遍。其他方面同上题。 ```cpp void Sort(int k) { for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i]; sort(t + st[k], t + ed[k] + 1); } void PushDown(int x) { if (dlt[x] != 0x3f3f3f3f3f3f3f3fll) for (int i = st[x]; i <= ed[x]; i++) a[i] = t[i] = dlt[x]; dlt[x] = 0x3f3f3f3f3f3f3f3fll; } void Modify(int l, int r, int c) { int x = belong[l], y = belong[r]; PushDown(x); if (x == y) { for (int i = l; i <= r; i++) a[i] = c; Sort(x); return; } PushDown(y); for (int i = l; i <= ed[x]; i++) a[i] = c; for (int i = st[y]; i <= r; i++) a[i] = c; Sort(x); Sort(y); for (int i = x + 1; i < y; i++) dlt[i] = c; } int Binary_Search(int l, int r, int c) { int ans = l - 1, mid; while (l <= r) { mid = (l + r) / 2; if (t[mid] <= c) ans = mid, l = mid + 1; else r = mid - 1; } return ans; } int Answer(int l, int r, int c) { int ans = 0, x = belong[l], y = belong[r]; PushDown(x); if (x == y) { for (int i = l; i <= r; i++) if (a[i] <= c) ans++; return ans; } PushDown(y); for (int i = l; i <= ed[x]; i++) if (a[i] <= c) ans++; for (int i = st[y]; i <= r; i++) if (a[i] <= c) ans++; for (int i = x + 1; i <= y - 1; i++) { if (0x3f3f3f3f3f3f3f3fll == dlt[i]) ans += Binary_Search(st[i], ed[i], c) - st[i] + 1; else if (dlt[i] <= c) ans += size[i]; } return ans; } ``` ## 练习 1. [单点修改,区间查询](https://loj.ac/problem/130) 2. [区间修改,区间查询](https://loj.ac/problem/132) 3. [【模板】线段树 2](https://www.luogu.com.cn/problem/P3373) 4. [「Ynoi2019 模拟赛」Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048) 5. [「Violet」蒲公英](https://www.luogu.com.cn/problem/P4168) 6. [作诗](https://www.luogu.com.cn/problem/P4135)